【模板】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引理，我们可以知道，方案数为(frac{sum_{i=0}^{n-1}s[i]}{n})%(mod)
于是我们可以打出代码:
#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
",ans);
}
return 0;
}
然后，它就T了。。。qwq
那么，我们该怎么优化这个程序呢？
————————————————以下是正文——————————————————
我们不难注意到，对于使得gcd(n,i)相同的i，对答案的贡献是一样的(先不管除以n)，为n^gcd(n,i)，那么，我们不妨就枚举gcd(n,i)!
因为枚举gcd(n,i)等价与枚举n的约数，所以，我们枚举部分的复杂度就降为了(O(sqrt{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
",ans);
}
return 0;
}