置换群和Polya定理：poj1026,poj1286,poj2409,poj3270 八月 19th, 2009
继续刷Ulm的入门题，做到poj2409，顺便去啃了下Polya定理，然后按照某份poj题目分类列表把置换群和Polya定理的题都做了。
一开始我是看《组合数学的算法与程序设计》这本书的，后来发现证明过程直接晕了，然后去翻《信息学竞赛与算法艺术》，发现说的非常简略，但是结合《组合数学的算法与程序设计》上面的，瞬间看懂了……刘汝佳的黑书果然是需要配合其他书来看的~
KEYNOTE:
群：（在某运算下）封闭性、结合律、单位元、逆元
置换：（换来换去=+=）
置换群：元素是置换，运算是置换的连接
循环：a1->a2->a3->……->an->a1的置换，任何置换可分解成循环的乘积。
循环节数：置换表示成循环乘积形式后循环的个数
两个循环一对元素换位后合并
一个循环一对元素换位后拆分
等价类：所有通过置换群中置换可以相互置换的状态为同一等价类
Burnside引理：把有限集X作用在置换群G上，等价类数目为各个置换下不变的元素个数/置换个数(1)
循环->用k个颜色给有限集X染色不变的方案数=k^置换的循环节数(2)
(1)+(2)->Polya定理：用k个颜色给有限集X染色的集合在G下的等价类数目=sigma(k^置换的循环节数)/置换个数
pku/poj 1026 Cipher 题解/解题报告：
一看就是一个置换，执行次数有点多，只需要先把置换拆分成循环，然后执行每个循环k%循环长度次即可
话说这题我有点纠结，执行循环的时候想了半天不另开数组怎么做，最后还是放弃了=+=
pku/poj 1286 Necklace of Beads 题解/解题报告：
标准Polya定理计算，没变要把置换都算出来，因为可以知道共l个点旋转i个点的置换的循环节数为gcd(i,l)，长度为偶数时翻转置换有两种，循环节数分别为l/2和l/2+1，奇数时为l/2+1，利用Polya公式可直接算出。注意用64位的数据类型
pku/poj 2409 Let it Bead 题解/解题报告：
除了染色数不固定为3外同1286
pku/poj 3270 Cow Sorting 题解/解题报告：
先排序得出置换，然后拆分成循环
对于一个循环，有两种策略：
1：只利用循环内元素，显然每次取最小元素与其他交换最优
2：利用外部元素，显然应先取所有元素里最小的与本循环最小元素交换，然后代替本循环最小元素交换其他的，然后再换回去
计算都不复杂，对于每个循环取这两者中较优的即可