Polya/Burnside计数

发布于 2018-03-06  3.48k 次阅读


这一部分主要涉及的是一类计算本质不同方案的计数问题,那么先来简述一下这两个定理的内容:

Burnside:本质不同的方案数等于每种置换下不变元素个数之和除以置换数。

Polya:n个点可以染m种颜色的方案数,等于m的置换的循环节次方之和除以置换数。

仔细想一下这两个好像是一个东西,本质上就是规定给每个循环节染成相同的颜色来保证在该种置换下元素不变,然后计算方案数。

 

BZOJ 1004:[HNOI2008]Cards 

由于置换数比较少,我们可以得到每个置换的循环节数以及大小,那么对于每种置换,只要规定每个循环节染成相同的颜色然后计算可行的方案数即可。对于方案数的计算,可以用三维的背包来做。

(据说这道题还有些性质,甚至不用管输入,反正我是不太明白)

 

BZOJ1547:周末晚会

给长度为n的环黑白染色,要求黑色不能连续出现超过K块,求方案数。

首先,对于环状的问题,有一些性质需要使用:

1.转i次会产生gcd(i,n)个循环节。在一个环上每次跳i步,需要跳lcm(i,n)的长度才能跳回原位,跳的步数是lcm(i,n)/i,而每一步经过的点一定互不相同(否则就是走回了原位),也就是说循环节的元素个数(长度)是lcm(i,n)/i=n/gcd(i,n),那么循环节的个数就是gcd(i,n)。

2.环上相邻的元素所属的循环节交替出现。也就是说设循环节个数为x,那么从环中随便截取长度为x的一段,一定能包含所有的循环节。画画图就可以看出来。

3.循环节个数为i的置换有phi(n/i)个。写写式子就可以看出来。

对于这道题,我们只要枚举循环节的个数x,然后考虑长度为x的一段内的方案数,就可以知道一种置换下不变元素的个数。预处理出g[i][j]:长度为i的序列,第一个元素强制不选,最后j个元素强制选择的方案数。f[i][j]:g[i][j]的前缀和。那么,对于每一个枚举的循环节数,只要枚举段首选择的数目,再让剩下的部分最后选的元素个数小于定值即可。

 

BZOJ1815:[Shoi2006]color 有色图 && BZOJ1478:Sgu282 Isomorphism

比较神的题,感觉思想类似于“二元组”的置换。首先,定义边(i,j)的置换就是两端点置换形成的二元组(p[i],p[j]),点的置换对应唯一的边的置换,那么可以按照两端点所处的循环节来给边的置换分类。对于两点同处于一个循环节里的边,边的置换的循环节的个数就是点的循环节的长度的一半。考虑枚举边的两端点在环中的距离,最多有L/2种。对于两点不处于同一个循环节的情况,边的循环节个数就是gcd(L1,L2)。首先点对有L1*L2个,而边的循环节长度是lcm(L1,L2)(好比说是齿轮咬合回到原位所经过的长度),除一下就是gcd(L1,L2)。

有了上面的结论,如果我们确定了点的置换的循环节个数及每个循环节的长度,就可以计算出对应的边的置换数,就可以上Polya定理了。那么,我们可以枚举点置换的每个循环节的长度,只要确定每种情况对应的点的置换数即可。设枚举出的长度为L1....Lm。

$$置换数=\frac {  \prod C_{n}^{L_1} C_{n-L_1}^{L2}.....C_{n-L_1-L_2-.....-L_{m-1}}^{L_m} \; * \prod_{i=1}^{m} (L_i-1)! \; }{ \prod k_{i}} $$

第一个乘积就是把n个点分成m组的方案数,第二部分就是对于每一个循环节,有长度-1的阶乘种循环顺序(考虑循环中每个点都可作为起点,而每个起点出发可以走向其他任意一点,一直走下去,每次可选择的点数减少1),最后一部分的k就是每种长度相同的组数,因为每种分组都是等价的,不存在先后关系。

化简以后就是:

$$\frac {n!}{\prod_{i=1}^{m}L_i \prod _{j} k_j}$$

这样,搜出来点的循环节长度,算出这种情况下点的置换数,因为边的置换对应点的置换,所以边的置换数就知道了,而我们还知道每一种这样的边的置换对应的循环节数,那么直接上Polya定理就可以得到结果了。

 

POJ2154 Color

还是循环染色,但是数据范围到了1e9,直接枚举gcd即可。由于不存在逆元,在乘方的时候要少一次。卡常差评。

 

POJ2888 Magic Bracelet

还是循环染色,但是限制某些元素不能相邻。m很小,矩阵乘算一段的方案数。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974