nullPólya计数法的应用Pólya计数法的应用南京外国语学校 陈瑜希问题描述问题描述06年江苏上海选拔赛
染色图是无向完全图，且每条边可被染成k种颜色中的一种。
两个染色图是同构的，当且仅当可以改变一个图的顶点的编号，使得两个染色图完全相同。
问N个顶点，k种颜色，本质不同的染色图个数（模质数N
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
数：
分析分析这个算法十分直观，直接套用了Pólya定理，但需要枚举每个对于点的置换，并求循环数。时间复杂度为 O(N!N2)。
对于本题N≤53的数据范围，这个算法会超时。分析分析再进一步分析问题，会发现，其实这N!个置换中，有许多是类似的，比如：null分析分析观察这些对于点的置换，发现它们都是由一个长度为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)分析分析假设点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)!种方案又是重复的，所以还要除以(j-i+1)!分析分析所以总的置换个数就是
每个循环的长度为L
每组Li=Li+1=…Lj s为j-i+1分析分析需要计算很多T2-1，其中T2很大，而且是-1次的，难道要分解质因数了吗？
P是质数，且满足N
本文档为【pálya计数法的应用】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483