polya 计数法，burnside定理 学习小结
转载自：http://hi.baidu.com/%B1%BF%D0%A1%BA%A2_shw/blog/item/89fd091055caf51db9127bc8.html
记得最早接触这类题目还是去年这个时候，当时看了点书，做了几个水题，就以为自己懂了。
后来发现自己还是根本没有理解。最近简单复习了下，又做了几道相关的题目。
但现在真的发现这个算法自己还是没有完全理解，只会简单地套公式，很多难的题目现在还是做不来，先整理一下，方便以后再复习吧。
ps ： 感谢 cuiaoxiang 及 AekdyCoin 给我的一些帮助。
先贴个模板：
int ans = 0;
for (int i = 1; i <= n; i++) if (n % i == 0) {
ans += fun(c, i) * euler(n / i);
}
if (n & 1) ans += n * fun(c, n / 2 + 1);
else ans += n / 2 * (fun(c, n / 2) + fun(c, n / 2 + 1));
cout << ans / (2 * n) << endl;
这个就是最裸的polya，用这个模板可以过：pku2409 【Let it Bead】
当n比较大的时候，这样直接枚举n就有点太暴力了，可以把n整数分解，直接去枚举他的因子即可。
再贴个模板：
void dfs(int step, int now, int n) {
if (step >= cnt + 1) {
ans = (ans + fun(n % mod, now - 1) * euler(n / now) % mod) % mod;
return;
}
for (int i = 0, t = 1; i <= c[step]; t *= p[step], i++)
dfs(step + 1, now * t, n);
}
用这个模板可以过： pku2154 【Color】
下面推荐一些简单的稍加变形的题目：
ps ： 以下代码中 Prime() 为求素数，divide() 为整数分解，euler() 为求欧拉函数，fun（）为求快速幂乘，matrix 为一个矩阵类（重载过乘号）。
pku2888 【Magic Bracelet】
这道题原来写过一个解题报告，具体见这里吧：【pku2888 （有限制条件的polay问题）】
hdu2865 【 Birthday Toy】
这题和上一题差不多，都是在颜色的关系上做了限制，要求一个环上相邻2个珠子的颜色不能相同，推出递推公式，用矩阵乘法就可以了。
int n, m;
long long ans;
long long cal(int k) {
long long cc = m - 1, ret;
if (k == 1) return 0;
if (k == 2) return cc * (cc - 1) % mod;
k -= 2;
matrix a, b;
a.mat[0][0] = 0;
a.mat[0][1] = 1;
a.mat[1][0] = cc - 1;
a.mat[1][1] = cc - 2;
FF(i, 0, 1) FF(j, 0, 1) b.mat[i][j] = (i == j) ? 1 : 0;
while (k) {
if (k & 1) b = b * a;
a = a * a;
k /= 2;
}
ret = (b.mat[1][1] * cc % mod) * (cc - 1) % mod;
return ret;
}
void dfs(int step, int now) {
if (step >= cnt + 1) {
ans = (ans + (long long)cal(now) * euler(n / now) % mod) % mod;
return;
}
for (int i = 0, t = 1; i <= c[step]; i++, t *= p[step])
dfs(step + 1, now * t);
}
int main(int argc, char** argv) {
Prime();
while (scanf("%d%d", &n, &m) != EOF) {
divide(n);
ans = 0;
dfs(1, 1);
ans = ans * fun(n, mod - 2) % mod;
ans = ans * m % mod;
printf("%d\n", ans);
}
return (EXIT_SUCCESS);
}
hdu3441 【 Rotation】
这题的设计还是很巧妙的，用了2次burnside，这题的关键在于 a 很大，不能直接枚举 b ，但其中b * b = a * a - 1，转化为分解（a + 1） 和 （a - 1），其他的都差不多了。
long long a, c, n, m, temp, ans;
void dfs_t(int step, long long now) {
if (step >= p1[0] + 1) {
temp = (temp + fun(m % mod, now) * euler(n / now) % mod) % mod;
return;
}
for (long long i = 0, t = 1; i <= c1[step]; t *= p1[step], i++)
dfs_t(step + 1, now * t);
}
void dfs(int step, long long now) {
if (step >= p1[0] + 1) {
long long b = now;
m = fun(c % mod, b * b);
m += fun(c % mod, ((b * b + 3) / 4)) * 2 % mod;
m += fun(c % mod, ((b * b + 1) / 2));
m %= mod;
m = m * inv_4 % mod;
n = (a * a - 1) / (b * b);
temp = 0;
dfs_t(1, 1);
temp = temp * fun(n % mod, mod - 2) % mod;
temp = temp * c % mod;
ans = (ans + temp) % mod;
return;
}
for (long long i = 0, t = 1; 2 * i <= c1[step]; t *= p1[step], i++) {
c1[step] -= 2 * i;
dfs(step + 1, now * t);
c1[step] += 2 * i;
}
}
void cal() {
divide(a - 1, p1, c1);
divide(a + 1, p2, c2);
for (int i = 1; i <= p2[0]; i++) {
bool f = false;
for (int j = 1; j <= p1[0]; j++) if (p2[i] == p1[j]) {
c1[j] += c2[i];
f = true;
break;
}
if (f == true) continue;
p1[0]++;
p1[p1[0]] = p2[i];
c1[p1[0]] = c2[i];
}
dfs(1, 1);
}
int main(int argc, char** argv) {
int T, ca = 0;
scanf("%d", &T);
Prime();
while (T--) {
scanf("%lld%lld", &a, &c);
ans = 0;
if (a == 1) ans = c;
else cal();
printf("Case %d: %d\n", ++ca, ans);
}
return (EXIT_SUCCESS);
}
hdu2481 【 Toy】
这题的难点同样是在一个确定的置换下如何确定合法的方案数。
这题感觉稍微有点难，我是参考一个大牛的解题报告后才做出来的。
具体参见这里吧：【解题报告】
long long cal(long long k) {
matrix a, c;
FF(i, 0, 2) FF(j, 0, 2) c.mat[i][j] = (i == j) ? 1 : 0;
a.mat[0][0] = 0;
a.mat[0][1] = 1;
a.mat[0][2] = 0;
a.mat[1][0] = -1;
a.mat[1][1] = 3;
a.mat[1][2] = 0;
a.mat[2][0] = 0;
a.mat[2][1] = 1;
a.mat[2][2] = 1;
k -= 1;
while (k) {
if (k & 1) c = c * a;
a = a * a;
k /= 2;
}
long long f = c.mat[1][1] % mod;
long long g = 2 * c.mat[2][1] % mod;
return (g + f) % mod;
}
void dfs(int step, int now) {
if (step >= cnt + 1) {
ans = (ans + mult((long long)cal(now), euler(n / now))) % mod;
return;
}
for (int i = 0, t = 1; i <= c[step]; i++, t *= p[step])
dfs(step + 1, now * t);
}
int main(int argc, char** argv) {
Prime();
while (cin >> n >> m) {
mod = n * m;
divide(n);
ans = 0;
dfs(1, 1);
ans = (ans / n % m + m) % m;
cout << ans << endl;
}
return (EXIT_SUCCESS);
}
还有不少比较难的题目，实在做不来了，等以后做了再补上吧。