发布时间：2024-09-29

置换群

Burnside定理

每个置换的不动点个数的平均值就是不同方案数

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类型数据的表示范围。并且两

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

色相同。

思路

1. 旋转置换。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}$
2. 翻转置换
   • 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为颜色数

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})$
• 暴力求欧拉函数即可

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";
}