題目大意：給定一個圓環上的n個點，圓環被分成360000度，點的位置由角度確定。然後用m種材料來填充這些點，某方案與它旋轉的方案同構，問不同構的方案數。m <= 1000,n <= 360000
解題思路：外國佬的題目晦澀難懂,看了好多遍才能理解%70的題意，然後敲了一遍交wa掉了。爾後又看了好多遍，終於大徹大悟。
Polya的核心是求置換。這題和普通的項鏈計數不同，難點是如何旋轉，因為給的角度不一定等分整個圓環，等分的話就有n個置換和普通的項鏈計數一樣，那麼有些情況就只有一種置換，就是不變置換，比如10000，20000，40000，這三個怎麼旋轉都不會同構。上面的情況是最特殊的兩種情況，再考慮一種情況 45000 90000 225000 270000，這時候是有兩個置換，一個是不變置換，一個是旋轉180度的。
通過寫幾組特殊數據會發現其實這些點可以分成若干陀設為cnt陀（1<=cnt<=n)，如果這若干陀經過旋轉能和原來的重合，那麼他們就是同構的。每一陀個數為len = n / cnt，這len個點一共有m^len種填充方案。這時候問題轉換為一個有cnt個點的圓環，要用m^len種顏色填充，旋轉後的方案與它原來的方案同構，問不同的方案數,這種解法見這篇解題報告Here。
最後問題就是怎麼找cnt陀，再仔細想想會發現這其實和找一個字符串的最小覆蓋、循環節數問題一樣，可以通過求next數組來確定循環節數，cnt = n - next[n]。這個結論很優美，證明看Here。
這題不小心就跑了3s，不小心就成了Rank1.
測試數據：
Input:
2 4
0
120000
180000
270000
2 4
0
90000
180000
270000
100 5
0
45000
90000
180000
270000
2 4
45000
90000
225000
270000
OutPut:
16
6
99999307
10
C艹代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 360000
#define MAX 400000
#define MOD 100000007
#define int64 long long
//#define int64 __int64
int64 ans;
int n, m, angle[MAX]; www.2cto.com
int dist[MAX],next[MAX];
void Get_Next() {
//獲取next數組
int i,j,k;
i = 0; j = -1;
next[0] = -1;
while (i < n) {
if (j == -1 || dist[i] == dist[j])
i++,j++,next[i] = j;
else j = next[j];
}
}
int Get_NextLen() {
//len是循環節長度，cnt是循環節個數
int cnt = n;
int len = n - next[n];
if (n % len == 0)
cnt = n / len;
return cnt;
}
int Gcd(int x, int y) {
//返回最小公約數
int r = x % y;
while (r) {
x = y, y = r;
r = x % y;
}
return y;
}
int64 Eular(int64 n) {
//歐拉函數，返回小於n大於0與n互質的個數
int64 ans = n, i;
for (i = 2; i * i <= n; i++) {
if (n % i == 0) {
ans -= ans / i;
while (n % i == 0)
n /= i;
if (n == 1) break;
}
}
if (n != 1) ans -= ans / n;
return ans % MOD;
}
int64 Cal(int64 n, int64 k) {
//二分快速冪
int64 x = 1;
while (k) {
if (k & 1) x = (x * n) % MOD;
n = (n * n) % MOD, k >>= 1;
}
return x;
}
int64 inv(int64 x) {
//簡潔版求逆元
if (x == 1) return 1;
return inv(MOD % x) * (MOD - MOD / x) % MOD;
}
int64 Polya_2B(int64 m,int64 n) {
//優化後的方法，枚舉循環節個數i
int i, j, k;
ans = 0;
for (i = 1; i * i < n; ++i) //枚舉循環節個數
if (n % i == 0) {
ans = (ans + Eular(n / i) * Cal(m, i) % MOD) % MOD;
ans = (ans + Eular(i) * Cal(m, n / i) % MOD) % MOD;
}
if (i * i == n)
ans = (ans + Eular(n / i) * Cal(m, i) % MOD) % MOD;
return ans * inv(n) % MOD;
}
void input (int &a) {
char c, f;
while (((c = getchar()) < '0' || f > '9') );
for (a = 0; c >= '0' && c <= '9'; c = getchar())a = a * 10 + c - '0';
}
int main()
{
int i, j, k, t, cnt;
while (scanf("%d%d", &m, &n), n + m >= 0) {
for (i = 1; i <= n; ++i)
input(angle[i]);//scanf("%d", &angle[i]);
sort(angle+1,angle+1+n);
for (i = 1; i < n; ++i)
dist[i-1] = angle[i+1] - angle[i];
dist[n-1] = INF - angle[n] + angle[1];
Get_Next();
cnt = Get_NextLen();
ans = Polya_2B(Cal(m,n/cnt),cnt);
printf("%I64d\n", ans);
}
}
