发布时间：2024-07-31

Polya定理

设 G = {a1，a2，…，ag}是 N 个对象的置换群，用 M 种颜色给这 N 个
不同方案数为 $ \frac{m^{c(a_1)}+m^{c(a_2)+...+m^{c(a_g)}}}{|G|} ,其中c(a_i)$

POJ2409

题目大意：

给定M种颜色的珠子，每种颜色珠子的个数均不限，将这些珠子做成长度为N的项链。

问能做成多少种不重复的项链，最后的结果不会超过int类型数据的表示范围。并且两

条项链相同，当且仅当两条项链通过旋转或是翻转后能重合在一起，且对应珠子的颜

色相同。思路

旋转置换。k=0,1,2,..,n-1
- $ d=gcd(n,k),x+kt \equiv x(mod\ n) $
- $ kt \equiv 0 (mod\ n) $
- $ kt+nr=0 $
- $ t最少为\frac{n}{d} $
- $ \sum _{k=0}^{n-1}m^{d} $
翻转置换
- n为奇数，n个置换，每个置换对称点自己进行循环置换，任意两个数之间进行循环置换，共 $ \frac{n+1}{2} $，方案数为 $ nm^{\frac{n+1}{2}} $
- n为偶数，如果对称轴穿过某个点，$ \frac{n}{2}m^{\frac{n}{2}+1} $
- 对称轴在两点之间，$ \frac{n}{2}m^{\frac{n}{2}} $
- 旋转置换有n个，翻转也有n个，因此求平均数除以2n，此处m为颜色数

cpp

void solve(){
    int n;
    cin>>n;
    int res=0;
    for(int i=0;i<n;i++){
        int d=__gcd(n,i);
        res+=qpow(n,d);
    }
    if(n%2){
        res+=n*qpow(n,(n+1)/2);
    }
    else{
        res+=n/2*(qpow(n,n/2)+qpow(n,n/2+1));
    }
    cout<<res/(2*n)<<"\n";
}

【模板】Polya 定理

给定一个 $n$ 个点， $n$ 条边的环，有 $n$ 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 $10^9+7$ 取模。

注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。

n \leq 10^9

t \leq 10^3

思路

上题的简化版，但是数据范围增加
这题只有旋转置换， $ \frac{1}{n} \sum _{k=1}^nn^{gcd(n,k)}=\frac{1}{n} \sum _{d|n}n^d \sum _{k=1}^{\frac{n}{d}}[gcd(\frac{n}{d},k)==1]=\frac{1}{n} \sum _{d|n}n^d \phi(\frac{n}{d}) $
暴力求欧拉函数即可

cpp

int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}
int phi(int x){
    int ans=x;
    for(int i=2;i<=x/i;i++){
        if(x%i)continue;
        ans-=ans/i;
        while(x%i==0)x/=i;
    }
    if(x>1)ans-=ans/x;
    return ans;
}
void solve(){
    int n;
    cin>>n;
    int res=0;
    for(int d=1;d<=n/d;d++){
        if(n%d)continue;
        (res+=qpow(n,d)*phi(n/d)%mod)%=mod;
        if(d*d!=n){
            (res+=qpow(n,n/d)*phi(d)%mod)%=mod;
        }
    }
    cout<<res*qpow(n,mod-2)%mod<<"\n";
}

Polya定理 ​

POJ2409 ​

【模板】Polya 定理 ​

Polya定理

POJ2409

【模板】Polya 定理