题解 P4980 【【模板】Polya定理】

好题呢，不仅是单纯的Polya定理欸 0. 题目理解 可能是人弱的原因，一开始我把```本质不同的染色方案```理解成不仅要不能通过旋转与别的染色方案相同，还要不能通过翻转与别的染色方案相同，然后样例看不懂。实际上，```本质不同的染色方案```就**只需要不能通过旋转与别的染色方案相同。** 1. 在Polya定理之前——Burnside引理 burnside引理是polya定理的基础。 burnside引理大概是长这样的： --- 对于每个置换f，我们定义C(f)为在置换f下保持不变的方案数。 则有： 本质不同的方案数为C(f)的平均数。 $ans=\frac{1}{\left | G \right |} \sum _{f \in G} C(f)$ --- 并不是重点，就不细讲了。 然而Burnside引理需要枚举每个方案，会TLE。 2. Polya定理 我们知道对于每个置换f，我们一定能把它表示成循环的形式。那么我们定义L(f)为f的循环节数，k为颜色数(其实k=n)。根据该定理，则有$k^{L(f)}=C(f)$。那么问题就转化为了求L(f)。 这题很良心，置换只有旋转，于是可以简单解决，否则光是求L(f)就要O(n)了。同时，```|G|=n```首先我们设这是第i次旋转(初始状态算第一次旋转)，则有每个循环节长度为```lcm(n,i)/i```，那么```L(f)=n/(lcm(n,i)/i)```，即```L(f)=gcd(n,i)```。所以，$ans=\frac{1}{n} \sum _{f \in G} k^{gcd(n,i)}$ 3. 优化 然而我们发现，现在我们求每一个ans就已经是O(n)了，还有一个常数巨大的乘方，，，可能仅仅是每个测试点里的一组数据就超时，，然而我们还有一个t。。。 - 优化1：快速幂 应该都会吧，，不讲了。。。 - 优化2： 欧拉函数 我们可以从gcd优化。设$d_i=gcd(n,i)$。明显，所有d都是n约数。设有x个d是相等的，那么可以枚举n的约数。设枚举到了第j个约数$p_j$，那么$d=n/p_j$。我们也很容易发现$x=\varphi (n/d)$。所以$ans=\frac{1}{n} \sum _{p|n} \varphi (p)\times k^{\frac {n}{p}}$ 于是求ans只要$O(\sqrt n)$了 - 优化3：充分利用```k=n``` 其实这是一个主要目的为防止溢出的优化，但同时也对常数有一定优化。 在之前的算法中，我们因为要在算完$k^{L(f)}$的和后除以n，然而对于除法我们无法使用同余，所以不能在求和时取模，那么有很大的溢出风险。然而因为```n=k```，我们完全可以将k的指数减1，同时还解决了要处以n的尴尬，那么求和时完全是可以防止溢出的(为了稳妥起见，我用了```__int128```)。过程如下： $\because k=n$ $\therefore ans= \sum_{p|n}\frac{\varphi (p)\times k^{\frac {n}{p}}}{n}=\sum_{p|n}\frac{\varphi (p)\times n^{\frac {n}{p}}}{n}=\sum_{p|n}\varphi (p)\times n^{\frac {n}{p}-1}$ 好了，上代码： ```cpp #include<bits/stdc++.h> using namespace std; namespace FastIO{ //IO优化 char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } template<typename __Type_of__scan> void scan(__Type_of__scan &x){ __Type_of__scan f=1;x=0;char s=gc(); while(s<'0'||s>'9'){if(s=='-')f=-1;s=gc();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=gc();} x*=f; } char buf[100000],*pp=buf; void pc(const char c){ if(pp-buf==100000)fwrite(buf,1,100000,stdout),pp=buf; *pp++=c; } template<typename __Type_of__preprint> void fsh(__Type_of__preprint x){ if(x<0){pc('-');x=-x;} if(x>9)fsh(x/10); pc(x%10+'0'); } template<typename __Type_of__print> void print(__Type_of__print x){fsh(x);fwrite(buf,1,pp-buf,stdout);pp=buf;} } using namespace FastIO; typedef __int128 LL; const LL mod=1e9+7; LL qpow(LL x,LL y){ //快速幂 LL res = 1; while(y){ if(y&1) res = res*x%mod; x = x*x%mod; y >>= 1; } return res; } LL euler_phi(LL n) { //欧拉函数 LL res=1; for(LL i=2; i*i<=n; i++) if(n%i==0) { n/=i,res=res*(i-1); while(n%i==0) n/=i,res=res*i; } if(n>1) res=res*(n-1); return res; } LL polya(LL m,LL n) { //polya定理主体 LL tot=0; for(LL i=1; i*i<=n; i++) { if(n%i) continue; tot+=euler_phi(i)*qpow(m,n/i-1); if(i*i!=n) tot+=euler_phi(n/i)*qpow(m,i-1); } return tot%mod; } int main(){ int t; scan(t); for(;t;--t){ LL n; scan(n),print(polya(n,n)),pc('\n'); } } ```