pálya计数法的应用

Pólya计数法的应用南京外国语学校陈瑜希问题描述•06年江苏上海选拔赛•染色图是无向完全图，且每条边可被染成k种颜色中的一种。•两个染色图是同构的，当且仅当可以改变一个图的顶点的编号，使得两个染色图完全相同。•问N个顶点，k种颜色，本质不同的染色图个数（模质数NP109）。•N≤53问题描述问题描述问题描述•N=3K=2简单分析•枚举会超时•普通的乘法原理无法求解Burnside引理•设G是置换群，C是G的着色集合。•C中的不等价着色数为：使着色通过G中的置换保持不变的着色的平均数。sjjaDGAnswer1)(||1Pólya定理•假设有k种不同的颜色，某个置换的循环数为c，则对于这个置换，通过它保持不变的着色数为，k的c次方。)()(jacjkaD例题分析•放在这个问题中，置换群中的对象就是所有的边，染成k种颜色，G就是由点的置换引起的边的置换的群。分析•例如N=3时一共有3条边。•点的不同排列有3!=6种。•由点的置换而引起的对应的边的置换如下：)3,2(),3,1(),2,1()3,2(),3,1(),2,1(3,2,13,2,1)3,2(),2,1(),3,1()3,2(),3,1(),2,1(2,3,13,2,1)3,1(),3,2(),2,1()3,2(),3,1(),2,1(3,1,23,2,1)3,1(),2,1(),3,2()3,2(),3,1(),2,1(1,3,23,2,1)2,1(),3,2(),3,1()3,2(),3,1(),2,1(2,1,33,2,1)2,1(),3,1(),3,2()3,2(),3,1(),2,1(1,2,33,2,1)2,1(),3,2(),3,1()3,2(),3,1(),2,1(2,1,33,2,1分析•先求出每个置换的循环数c•根据Pólya定理，可求出本质不同的方案数：sjacjkGAnswer1)(||1分析•这个算法十分直观，直接套用了Pólya定理，但需要枚举每个对于点的置换，并求循环数。时间复杂度为O(N!N2)。•对于本题N≤53的数据范围，这个算法会超时。分析•再进一步分析问题，会发现，其实这N!个置换中，有许多是类似的，比如：)3,2(),2,1(),3,1()3,2(),3,1(),2,1(2,3,13,2,1)3,1(),3,2(),2,1()3,2(),3,1(),2,1(3,1,23,2,1)2,1(),3,1(),3,2()3,2(),3,1(),2,1(1,2,33,2,1分析•观察这些对于点的置换，发现它们都是由一个长度为1和一个长度为2的循环组成。•显然它们对应的边的置换，也是类似的。如果把每个置换都处理一遍，是很浪费的。•这3个，只要处理一个即可。分析•枚举出所有本质不同的对于点的置换，并对每种置换求下面2个值–1、该种置换的对应边的置换的循环节数–2、与该种置换类似的置换总数分析•要保证枚举出来的对于点的置换各不相同，只需枚举它的所有循环节长度，设为Li，并保证•0＜L1≤L2≤…≤Lm•L1+L2+…+Lm=N•N=53时，一共要需要枚举329921种不同情况。分析•然后需要把对应点的循环信息转化成对应边的置换的循环节数分析•假设点i与点j同属于一个长度为L的循环中，则(i,j)组成的置换中循环节个数为•有一个长度为5的循环(1,2,3,4,5)•(1,2),(2,3),(3,4),(4,5),(5,1)•(1,3),(2,4),(3,5),(4,1),(5,2)2L分析•假设点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个圆排列问题，可知一共有mLLLN...!21种不同方式。分析•如果有Li=Li+1=…=Lj，那么每(j-i+1)!种方案又是重复的，所以还要除以(j-i+1)!分析•所以总的置换个数就是•每个循环的长度为L•每组Li=Li+1=…Ljs为j-i+1!!...!...!2121tmsssLLLN分析•需要计算很多T2-1，其中T2很大，而且是-1次的，难道要分解质因数了吗？•P是质数，且满足NP。•所以T2也与P互质•由数论知识可知：•T2p-1≡1(modp)•T2-1≡T2p-1×T2-1=T2p-2(modp)•所以可以把T2-1转化为求T2p-2，可用倍增的方法在O(Logp)的时间内求解。本题总结•这个问题遇到了这样的困难：•置换的个数偏多而导致不能对每个置换都算其循环数•解决的方法，就是找出置换群中相似的置换，而不重复计算•这个去除冗余运算的方法在Pólya计数问题中经常用到•对于每类相似置换个数的计算，也需要扎实的数学功底。全文总结•信息学竞赛中经常出现这类问题。比如–Transportationisfun(spoj419)–He’sCircles(sgu294)–Cubes(uva10601)•它们在直接使用公式时往往会遇到一些困难。这些困难虽然不同，但也有一些相似之处。全文总结•Pólya计数法不仅仅能解决许多计数问题，它的证明过程也是相当有意思的。•灵活使用Pólya计数法，不仅仅需要熟练掌握此类问题的性质，还要有扎实的数学功底和分析问题能力。•数学方法是解决问题的工具，而分析问题能力是算法的源泉。分析•下面讨论一下如何计算：•一部分是MT1，其中T1并不大，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为中的一种着色，那么与c等价的着色数等于G中的置换个数除以c的稳定核中的置换个数。证明•设f是G中的一个置换，根据定理1，满足g*c=f*c的置换g实际上就是中的那些置换。•由消去律，则从fh=fh’得到h=h’。•集合中的置换个数等于G(c)中置换的个数。•因为总共有|G|个置换，所以，与c等价的着色数等于证明•我们要数使f保持c不变即f*c＝c的对偶(f,c)的个数。证明•一种计数的方式是考察G中的每个f，并计算f保持着色不变的着色数，然后相加所有的量。设D(f)是通过f保持着色不变的着色集，所以用这种方式计数得到sjjaDGL1)(||1证明•另一种计数的方式按等价类将着色归类。•在同一等价类中，两种着色对和贡献了同样的量，每个等价类的总贡献是|G|。•因此，不同等价类数目就是：•通过每个置换保持着色不变的着色除以置换总数。证明•要得到在置换下稳定不动的方案，即把置换的每个循环节都染上相同的颜色。•假设有k种不同的颜色，某个置换的循环数为c，则对于这个置换，通过它保持不变的着色数为，k的c次方。