2、放在这个问题中，置换群中的对象就是所有的边，染成k种颜色，G就是由点的置换引起的边的置换的群。分析例如N=3时一共有3条边。点的不同排列有3!=6种。由点的置换而引起的对应的边的置换如下：分析先求出每个置换的循环数c根据Pólya定理，可求出本质不同的方案数：分析这个算法十分直观，直接套用了Pólya定理，但需要枚举每个对于点的置换，并求循环数。时间复杂度为O(N!N2)。对于本题N≤53的数据范围，这个算法会超时。分析再进一步分析问题，会发现，其实这N!个置换中，有许多是类似的，比如：分析观察这些对于点的置换，发现它们都是由一个长度为1和一个长度为2的循环组成。显然它们对应的边的置换，
3、也是类似的。如果把每个置换都处理一遍，是很浪费的。这3个，只要处理一个即可。分析枚举出所有本质不同的对于点的置换，并对每种置换求下面2个值1、该种置换的对应边的置换的循环节数2、与该种置换类似的置换总数分析要保证枚举出来的对于点的置换各不相同，只需枚举它的所有循环节长度，设为Li，并保证0＜L1≤L2≤…≤LmL1+L2+…+Lm=NN=53时，一共要需要枚举329921种不同情况。分析然后需要把对应点的循环信息转化成对应边的置换的循环节数分析假设点i与点j同属于一个长度为L的循环中， 则(i,j)组成的置换中循环节个数为有一个长度为5的循环(1,2,3,4,5)(1,2),(2,3),
4、(3,4),(4,5),(5,1)(1,3),(2,4),(3,5),(4,1),(5,2)分析假设点i与点j各属于长L1和L2的两个不同循环中，则这样的边(i,j)组成的置换中循环节个数为(L1,L2)。(1,2)(3,4,5,6)(1,3),(2,4),(1,5),(2,6)(1,4),(2,5),(1,6),(2,3)分析还需要求出与其类似的置换数假设已确定了0＜L1≤L2≤…≤Lm，接下来就是将1…N这N个点分别放入这m个循环节中，满足第i个循环中恰含有Li个点，这相当于m个圆排列问题，可知一共有种不同方式。分析如果有Li=Li+1=…=Lj，那么每(j-i+1)!种方案又是重复
5、的，所以还要除以(j-i+1)!分析所以总的置换个数就是每个循环的长度为L每组Li=Li+1=…Ljs为j-i+1分析需要计算很多T2-1，其中T2很大，而且是-1次的，难道要分解质因数了吗？P是质数，且满足N6、到对于每类相似置换个数的计算，也需要扎实的数学功底。全文总结信息学竞赛中经常出现这类问题。比如Transportationisfun(spoj419)He’sCircles(sgu294)Cubes(uva10601)它们在直接使用公式时往往会遇到一些困难。这些困难虽然不同，但也有一些相似之处。全文总结Pólya计数法不仅仅能解决许多计数问题，它的证明过程也是相当有意思的。灵活使用Pólya计数法，不仅仅需要熟练掌握此类问题的性质，还要有扎实的数学功底和分析问题能力。数学方法是解决问题的工具，而分析问题能力是算法的源泉。谢谢大家!分析下面讨论一下如何计算：一部分是MT1，其中T1并不大，
7、MT1modP可以用倍增的思想在log(T1)时间内计算。证明设c为中的一种着色，那么与c等价的着色数等于G中的置换个数除以c的稳定核中的置换个数。证明定理1：对于每一种着色c，c的稳定核G(c)是一个置换群，而且对G中任意置换f与g，g*c=f*c当且仅当f-1g属于G(c)。证明假设f*c=g*c则所以f-1g使c不变，因此，f-1g属于G(c)。反之，假设f-1g属于G(c)，通过类似的计算可证得f*c=g*c证明推论：设c为
