Polya

发表于 | 更新于 | 评论数： | 阅读次数： | 阅读次数：
本文字数： 3.2k | 阅读时长 ≈ 6 分钟

Polya

有关于这个polya（波利亚）公式,其实我只能看懂一点，但是解释不了，因此就从网上拉了一篇博客，感觉写的挺好，你们可以借鉴一下 polya

公式

方案总数: $\frac{旋转置换+翻转置换}{置换群}$

旋转置换:
方案数: $k^{gcd(n,i)}$

一个长度为n的环，每 i 个染同一种颜色，可以染多少种颜色。

假设起点在x，则x，x+i，x+2i，……，x+ki，……

假设在第t次，第一次回到起点，则x=(x+ti)%n => ti%n=0 => t=$\frac{LCM(i,n)}{i}$=$\frac{\frac{n*i}{GCD(n,i)}}{i}$=$\frac{n}{GCD(n,i)}$。

那么可以上$\frac{n}{t}$种颜色，即$\frac{n}{\frac{n}{GCD(n,i)}}$种，所以旋转的着色方案有种$k^{gcd(n,i)}$。

翻转置换:

方案数：n$k^{\frac{n+1}{2}}$或者$\frac{n}{2}$$k^{\frac{n}{2}+1}+k^{\frac{n}{2}}$

当 n 为奇数时，对称轴为 某点-对边中点 ，显然这样置换有 n 种，每个置换有 $\frac{n+1}{2}$ 个循环。因此答案为 n$k^{\frac{n+1}{2}}$；
当 n 为偶数时，对称轴为 某点-对点 时，置换有$\frac{n}{2}$ 种，每个置换有$\frac{n}{2}$+1 个循环；对称轴为 某边-对边中点 时，置换有 $\frac{n}{2}$ 种，每种置换有 $\frac{n}{2}$个循环。因此答案为$\frac{n}{2}$$k^{\frac{n}{2}+1}+k^{\frac{n}{2}}$。

题目

来几道题目吧

HDU 1817

很裸的Polya定理应用，用一下上面的公式就行了

珠子可以染的颜色固定为3种，然后n颗珠子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//注意特判0的情况
/*quick_power（） 为求幂，可以直接用pow（但是这个要记得类型转换，不推荐使用），也可以用快速幂，本人采用的是快速幂*/
if(n==0){
    cout<<0<<endl;
    continue;
}
m=3;
ll sum=0;
ll ans=0;
for(int i=1;i<=n;i++){
    sum=__gcd(n,i);
    ans+=quick_power(m,sum);
}
if(n%2) ans=ans+n*quick_power(m,(n+1)/2);
else ans=ans+n/2*(quick_power(m,n/2)+quick_power(m,n/2+1));
cout<<ans/(n+n)<<endl;

POJ 2409

很裸的Polya定理应用，用一下上面的公式就行了

1
2
3
4
5
6
7
8
9
10
/*quick_power（） 为求幂，可以直接用pow（但是这个要记得类型转换，不推荐使用），也可以用快速幂，本人采用的是快速幂*/
ll sum=0;
ll ans=0;
for(int i=1;i<=n;i++){
    sum=__gcd(n,i);
    ans+=quick_power(m,sum);
}
if(n%2) ans=ans+n*quick_power(m,(n+1)/2);
else ans=ans+n/2*(quick_power(m,n/2)+quick_power(m,n/2+1));
cout<<ans/(n+n)<<endl;

POJ 2154

总思路：Polya+欧拉函数

这题要注意忽略的是旋转置换，因此只需要计算旋转置换就行了

1
2
3
4
5
6
7
8
9
10
// 这是种超时的写法，因为n太大了
cin>>n>>p;
m=n;
ll sum=0;
ll ans=0;
for(int i=1;i<=n;i++){
    sum=__gcd(n,i);
    ans+=power_mod(m,sum,p);
}
cout<<ans/(n)<<endl;

那么我们就需要进行优化了，当然是利用欧拉函数进行优化了

我们计算$n^{gcd(n,i)}$的时候，会发现有很多都是重复计算的，因为gcd(n,i)对于不同的i可能有一样的解，比如gcd(7,2)和gcd(7,3)是一样的，因此我们可以从这上面考虑节省时间。

接下来又是考验数学的时候了：

ans = $\frac{1}{n} \sum_{i=1}^{n}{n^{gcd(n,i)}}$

​ = $\frac{1}{n} \sum_{i|n}{\phi(\frac{n}{i}) n^{i}}$

​ = $\sum_{i|n}{\phi(\frac{n}{i}) n^{i-1}}$

然后问题就变成了求 $\phi(\frac{n}{i})$ ，套用一下欧拉函数的板子就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int Euler(int n){ //返回Euler(n)   
     int res=n,a=n;  
     for(int i=2;i*i<=a;i++){  
         if(a%i==0){  
             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出
             while(a%i==0) a/=i;  
         }  
     }  
     if(a>1) res=res/a*(a-1);  
     return res;  
}
int power_mod(int a,int b,int c)
{
    int ans=1;
    a=a%c;
    while(b!=0)
    {
        if(b&1)
            ans=(ans*a)%c;
        b>>=1;
        a=(a*a)%c;
    }
    return ans;
}

int main()
{
    int t;
    cin>>t;
    int n,p;
    int ans=0;
    while(t--){
    	cin>>n>>p;
    	ans=0;
    	for(int i=1;i*i<=n;i++){
    		if(i*i==n){
    			ans=ans+Euler(n/i)%p*power_mod(n,i-1,p)%p;
    			ans=ans%p;
    		}
    		else if(n%i==0){
    			ans=ans+Euler(n/i)%p*power_mod(n,i-1,p)%p+Euler(i)%p*power_mod(n,n/i-1,p)%p;
    			ans=ans%p;
    		}
    	}
    	cout<<(ans+p)%p<<endl;
    }
    return 0;
}