【模板】Polya定理 题解

提供一个新算法。。。

首先,我们来分析一下题目:

给一个有n个点的环图n种颜色,问本质不同的方案数

那么,很明显的,这是一个polya定理(废话,题目名说明了一切)

我们先来看看这道题的“操作”,很明显的操作就是只有一个——平移(有人说旋转,但我个人更喜欢看成平移。。。)

我们就可以开始枚举置换了

首先,我们枚举每次平移的单位长度,那么很明显的本质不同的平移有n种,分别是平移0-(n-1)个单位

可以发现,每一种平移方案就是一种置换

所以,我们可以枚举平移长度,假设现在单步平移i个单位,那么要使得序列"平移"回来,我们假设最少要k步。那么k一定满足:i*k%n==0,可以解得k=lcm(n,i)/i=n/gcd(n,i),所以就有n/k=gcd(n,i)个"循环",故而,根据polya定理,当前置换的"不动点"数为n(颜色数)^gcd(n,i),为了简写,我们把这一坨设为s[i]。

最后,由burnside引理,我们可以知道,方案数为%

于是我们可以打出代码:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
inline int ksm(int x,int y,int z){
    int ans=1;
    while(y){
        if(y&1){
            ans=(1LL*ans*x)%z;
        }
        x=(1LL*x*x)%z;
        y>>=1;
    }
    return ans%z;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        int ans=0;
        for(int i=0;i<n;++i){
            ans+=ksm(n,__gcd(n,i),mod);
            ans%=mod; 
        }
        ans=(1LL*ans*ksm(n,mod-2,mod))%mod;//逆元 
        printf("%d\n",ans);
    }
    return 0;
}

然后,它就T了。。。qwq

那么,我们该怎么优化这个程序呢?

————————————————以下是正文——————————————————

我们不难注意到,对于使得gcd(n,i)相同的i,对答案的贡献是一样的(先不管除以n),为n^gcd(n,i),那么,我们不妨就枚举gcd(n,i)!

因为枚举gcd(n,i)等价与枚举n的约数,所以,我们枚举部分的复杂度就降为了,所以,现在我们需要做的就是尽量快速的计算这个问题:

给出n的一个约数i,求0-(n-1)中有多少个数与n的gcd为i

我们先把i=1和i=n的情况算出来(为了方便)。

i=1时,满足条件的一共有φ(n)个,i=n时一个有一个(gcd(0,n)=n)

所以,这两个的答案和为Ans1=(φ(n)*n+n^n)%mod

那么,我们再来看看剩下的该怎么算

我们发现,求0-(n-1)中有多少个数与n的gcd为i,因为i不等于1和n,所以问题等价于

求1-n中有多少个数与n的gcd为i。

而我们可以发现,满足条件的数一定是i的倍数。所以,问题又等价于:枚举1-n/i中,有多少个数j满足gcd(n,j*i)=i

等价于求1-n/i中有多少个数j满足gcd(n/i,j)=1,很明显,这个问题的答案就是φ(n/i)

(为什么转化了这么多步啊!抓狂ing。。。)

那么,我们就需要较快的求φ(x)了

本来,我们可以通过预处理,用O(n)的时间求出所有的φ,但,问题是n<=1e9,时间上如果优秀的话,估计可能卡过,但空间上就明显不允许了,所以,我们必须找到一个较好的方法。

我们知道,φ是一个积性函数,所以,我们可以根据它的性质,找到它的一个质因数,然后递归求解。。。

参照杜教筛,我们可以先将较小的φ预处理出来(我是预处理到1e7)

然后,我们先用Miller_rabin算法判断x是否是质数,如果是,我们就返回x-1,否则,我们就可以用pollard_rho算法来分解x,递归求解,中间可以套个map来加速。问题得解。

当然,记得特判下n=1的答案(因为一开始我们同时统计了i=1和i=n的答案,于是对于1,就多算了一次)

半伪代码:

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,N=1e7+1;
map<int,int>f;
int T,fi[N],zhi[N>>1],e;
inline int ksm(int x,int y,int z){
    int ans=1;
    while(y){
        if(y&1){
            ans=(1LL*ans*x)%z;
        }
        x=(1LL*x*x)%z;
        y>>=1;
    }
    return ans;
}
inline void sai(int maxe){
    T=maxe;fi[1]=1;
    for(int i=2;i<=maxe;++i){
        if(!fi[i]){
            fi[i]=i-1;zhi[++e]=i;
        }
        for(int j=1;j<=e;++j){
            if(i*zhi[j]>maxe){
                break;
            }
            if(i%zhi[j]==0){
                fi[i*zhi[j]]=fi[i]*zhi[j];
                break;
            }
            fi[i*zhi[j]]=fi[i]*fi[zhi[j]];
        }
    }
}
inline bool Miller_rabin(int x){
    //偷懒省略 
}
inline int pollard_rho(int x){
    //偷懒省略 
}
inline int calc(int x){
    if(x<=T){
        return fi[x];
    }
    if(f.find(x)!=f.end()){
        return f[x];
    }
    int ret=pollard_rho(x);
    if(ret==x){
        return x-1;
    }
    return f[x]=((x/ret)%ret==0?ret*calc(x/ret):(ret-1)*calc(x/ret));
}
int main(){
    srand(1);
    sai(1e7);//预处理 
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);    
        if(n==1){
            puts("1");
            continue;
        }
        int ans=(ksm(n,n,mod)+(1LL*n*calc(n))%mod)%mod;
        for(int i=sqrt(n);i>=2;--i){//一次平移的距离
            if(n%i==0){
                ans+=(1LL*ksm(n,i,mod)*calc(n/i))%mod;
                ans%=mod;
                if(n/i!=i){
                    ans+=(1LL*ksm(n,n/i,mod)*calc(i))%mod;
                    ans%=mod;
                }
            }
        }
        ans=(1LL*ans*ksm(n,mod-2,mod))%mod;//逆元 
        printf("%d\n",ans);
    }
    return 0;
}