Algorithm

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

POJ-2409 Let it Bead and POJ-1286 Necklace of Beads

###POJ-2409 Let it Bead

m个珠子n种颜色,求一共能制造出多少串不同的珠子。

Pólya定理,先求置换群。

1.旋转置换

依次顺时针旋转1 ~ n个,循环个数为gcd(i, n)

2.翻转置换

当n为偶数时,分两种情况,一种是中心轴在两个对称对象上,则循环个数为n/2+1,另一种是对称轴两边分别有n/2个对象,则循环个数为n/2;

当n为奇数时,对称轴就只能在一个对象上,则循环个数为n/2+1;

UVA-10601 Cubes

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

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

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

正方体有24种置换。

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

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

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

Codeforces Round 172 (Div. 2)

###A. Word Capitalization

模拟之,将首字母变成大写。

###B. Nearest Fraction

按列出的范围暴力一下就行。

###C. Rectangle Puzzle

找出一个分界点角度,即两个矩形不重叠,但对角线重叠,分两种情况算。