置换群

POJ-2154 Color

置换群,burnside引理的题目。

这道题代表了一类题目的优化

裸的算法是 ∑n^(gcd(n,i)) 1<i<=n

复杂度过高,进行优化。

置换群种循环的个数L = n / gcd(n, i)

因为如果L | n, 则有n / L | n

则环的长度L的范围是1 ~ sqrt(L)

令a = gcd(n, i), 设i = at

则只有i与t互质的时候,gcd(i, t) = a

则最后可以优化为 ∑(Φ(i) * n ^ (i)) % p

UVA-10601 Cubes

题目是一个有限制的正方体棱的填色。

与其说是Pólya定理的题目,不如说是置换群的题目。

参考cxlove菊苣的题解才搞懂。。。

正方体有24种置换。

+静止不动
+体对角线上对立的顶点
+相对面的中心
+相对的楞中心连线

根据Burnside定理,本质不同的方案数为在每个置换下稳定不动的方案数处以总置换数。

而要得到置换下稳定不动的方案,即把置换的每个循环节染上想上相同的颜色。