Polya
有关于这个polya(波利亚)公式,其实我只能看懂一点,但是解释不了,因此就从网上拉了一篇博客,感觉写的挺好,你们可以借鉴一下 polya
公式
方案总数: 旋转置换+翻转置换置换群
旋转置换:
方案数: kgcd(n,i)
一个长度为n的环,每 i 个染同一种颜色,可以染多少种颜色。
假设起点在x,则x,x+i,x+2i,……,x+ki,……
假设在第t次,第一次回到起点,则x=(x+ti)%n => ti%n=0 => t=LCM(i,n)i=n∗iGCD(n,i)i=nGCD(n,i)。
那么可以上nt种颜色,即nnGCD(n,i)种,所以旋转的着色方案有种kgcd(n,i)。
翻转置换:
方案数:nkn+12或者n2kn2+1+kn2
当 n 为奇数时,对称轴为 某点-对边中点 ,显然这样置换有 n 种,每个置换有 n+12 个循环。因此答案为 nkn+12;
当 n 为偶数时,对称轴为 某点-对点 时,置换有n2 种,每个置换有n2+1 个循环;对称轴为 某边-对边中点 时,置换有 n2 种,每种置换有 n2个循环。因此答案为n2kn2+1+kn2。
题目
来几道题目吧
HDU 1817
很裸的Polya定理应用,用一下上面的公式就行了
珠子可以染的颜色固定为3种,然后n颗珠子
1 | //注意特判0的情况 |
POJ 2409
很裸的Polya定理应用,用一下上面的公式就行了
1 | /*quick_power() 为求幂,可以直接用pow(但是这个要记得类型转换,不推荐使用),也可以用快速幂,本人采用的是快速幂*/ |
POJ 2154
总思路:Polya+欧拉函数
这题要注意忽略的是旋转置换,因此只需要计算旋转置换就行了
1 | // 这是种超时的写法,因为n太大了 |
那么我们就需要进行优化了,当然是利用欧拉函数进行优化了
我们计算ngcd(n,i)的时候,会发现有很多都是重复计算的,因为gcd(n,i)对于不同的i可能有一样的解,比如gcd(7,2)和gcd(7,3)是一样的,因此我们可以从这上面考虑节省时间。
接下来又是考验数学的时候了:
ans = 1n∑ni=1ngcd(n,i)
= 1n∑i|nϕ(ni)ni
= ∑i|nϕ(ni)ni−1
然后问题就变成了求 ϕ(ni) ,套用一下欧拉函数的板子就行了
1 | int Euler(int n){ //返回Euler(n) |
v1.5.2