首页 > ACM题库 > HDU-杭电 > HDU 4187-Alphabet Soup[解题报告]HOJ
2015
05-23

HDU 4187-Alphabet Soup[解题报告]HOJ

Alphabet Soup

问题描述 :

Peter is having lunch at home. Unfortunately for him, today’s meal is soup. As Peter’s mother is aware that he doesn’t like it very much, she has cooked a special soup using pasta pieces shaped like letters from the alphabet, numbers and other characters. She has a special knife with which she can prepare an unlimited supply of pasta pieces that may come in S di fferent forms. The soup always has P pasta pieces in it, and is so thick that the pieces never move.
Despite her eff orts, Peter is still not happy with today’s menu and asks how many days in his life he will have to eat soup. His mother promises him that she will prepare a di fferent soup every day, and that on no day will the dish contain the same shapes in all positions as any soup dish previously served. However, the number P of pasta pieces, as well as the positions in which pieces float, will remain the same every day. Peter is not easily fooled (or so he thinks), and he cleverly realizes that this can still make him eat soup for ages. In an attempt to reduce the number of confi gurations, he tells his mother he will not accept any dish which can be obtained by rotating one of the con figurations previously seen.
Numbers Game

Figure 1: Top view of Peter’s dish

Consider the dish as a circle of radius 2 centered at the origin. All the symbols will be floating in the soup at a given angle (in millidegrees) at distance 1 from the origin. Two plates are considered equal if you can perform a rotation of one of the dishes about its center so that the positions of the symbols, as well as the symbols themselves, are the same in both.
Your program will be given the number of possible symbols Peter’s mother has available, and the angles determining the location of each of the pasta pieces (measured clockwise in millidegrees). Write a program that returns the number of possible plates Peter’s mother can prepare. As this number can be very large, output the number modulo 100,000,007, which is prime.

输入:

The fi rst line of input in each test case contains two numbers: S (2<=S<=1,000), the number of symbols Peter’s mother can use; and P (P > 0), the number of pasta pieces floating in the soup. Each of the next P lines contain the angle A (0<=A <360,000) of one of the P pieces (measured clockwise in millidegrees). All angles will be di fferent.
Di fferent tests cases are separated by a blank line. After the last test case there is a line with S = P = -1.

输出:

The fi rst line of input in each test case contains two numbers: S (2<=S<=1,000), the number of symbols Peter’s mother can use; and P (P > 0), the number of pasta pieces floating in the soup. Each of the next P lines contain the angle A (0<=A <360,000) of one of the P pieces (measured clockwise in millidegrees). All angles will be di fferent.
Di fferent tests cases are separated by a blank line. After the last test case there is a line with S = P = -1.

样例输入:

2 4
0
90000
180000
270000

100 5
0
45000
90000
180000
270000

-1 -1

样例输出:

6
99999307

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define MOD 100000007
#define PRIME_SIZE 500005
#define _int64 long long

using namespace std;
int prime[PRIME_SIZE], phi[PRIME_SIZE];
bool primes[PRIME_SIZE];
void Euler_primes_phi_mu()
{
	phi[1]=1;
	for (int i=2; i<PRIME_SIZE; i++)
	{
		if (primes[i]==0)
			phi[i]=i-1, prime[++prime[0]]=i;
		for (int j=1; j<=prime[0] && prime[j]*i<PRIME_SIZE; j++)
		{
			primes[prime[j]*i]=true;
			if (i%prime[j]==0) { phi[i*prime[j]] = phi[i]*prime[j]; break; }
			phi[i*prime[j]] = phi[i]*(prime[j]-1);
		}
	}
}
_int64 GCD(_int64 a, _int64 b) { for (_int64 t; a%b; t=a%b, a=b, b=t) ; return b; }
_int64 pow_mod(_int64 a, _int64 n)
{
	_int64 ans=1;
	for (; n; n>>=1, a=(a*a)%MOD) if (n&1) ans=(ans*a)%MOD;
	return ans;
}
_int64 polay(int n, int base)
{
	_int64 ans=0;
	for (int i=1; i*i<=n; i++)
		if (n%i==0)
		{
			ans=(ans+pow_mod(base, i)*phi[n/i])%MOD;
			if (i*i!=n)
				ans=(ans+pow_mod(base, n/i)*phi[i])%MOD;
		}

	ans=(ans*pow_mod(n, MOD-2))%MOD;
	return ans;
}
int next[PRIME_SIZE], N[PRIME_SIZE], d[PRIME_SIZE];
void Pre_next(int *s, int len)
{
	int i, j=0;
	for (next[0]=-1, i=2; i<=len; i++)
	{
		while (j>-1 && s[i-1]!=s[j]) j=next[j];
		next[i]=++j;
	}
}
int main()
{
	//freopen("1.txt", "r", stdin);
	Euler_primes_phi_mu();
	int n, m, i;
	
	while (scanf("%d %d", &m, &n), ~m)
	{
		for (i=1; i<=n; i++) scanf("%d", &N[i]);
		sort(N+1, N+n+1); N[n+1]=N[1]+360000;
		
		for (i=1; i<=n; i++) d[i-1]=N[i+1]-N[i];
		Pre_next(d, n);
		int dif=n-next[n];
		_int64 gcd;
		if (n%dif==0) gcd=GCD(n, dif);
		else gcd=n;
		_int64 ans=polay(n/gcd, pow_mod(m, gcd));
		printf("%I64d\n", ans);
	}
	return 0;
}