LG4980 【模板】Polya定理

佚名 6年前 (2019-04-11) 随笔 711人围观抢沙发百度已收录

题意

题目描述

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

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入输出格式

输入格式：

第一行输入一个$t$，表示有$t$组数据

第二行开始，一共$t$行，每行一个整数$n$，意思如题所示。

输出格式：

共$t$行，每行一个数字，表示染色方案数对$10^9+7$取模后的结果

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

说明

$$n \leq 10^9$$ $$t \leq 10^3$$

分析

先找不动点个数公式。考虑循环移动$i$位这个置换，把珠子循环编号。由于移动后编号要重复，所以最大的编号一定是$\textrm{lcm}(i,m)$。所以一个循环里面的珠子个数就是$\frac{\textrm{lcm}(i,m)}{i}=\frac{n}{\gcd(i,n)}$。所以共有$\gcd(i,n)$个循环。因此不动点个数是$n^{\gcd(i,n)}$

所以答案式为
\[ \frac 1n\sum_{i=0}^{n-1}n^{\gcd(i,n)} \\ =\frac 1n\sum_{d|n}\varphi(\frac nd)n^d \\ =\sum_{d|n}\varphi(d) n^{\frac nd-1} \]

我并不知道先枚约数再算欧拉函数的复杂度是多少，反正约数个数怎么也达不到$O(\sqrt{n})$的上界。
即使$2^3*3*5*7*11*13*17*19*23=892371480$，这个数也只有1024个约数，小于$\sqrt{892371480}=29872.587433$。

代码

#include<bits/stdc++.h>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
    rg T data=0,w=1;rg char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') w=-1;ch=getchar();}
    while(isdigit(ch)) data=data*10+ch-'0',ch=getchar();
    return data*w;
}
template<class T>il T read(rg T&x) {return x=read<T>();}
typedef long long ll;

co int mod=1e9+7;
il int add(int x,int y) {return (x+=y)>=mod?x-mod:x;}
il int mul(int x,int y) {return (ll)x*y%mod;}
int fpow(int x,int k){
    int re=1;
    for(;k;k>>=1,x=mul(x,x))
        if(k&1) re=mul(re,x);
    return re;
}
int phi(int n){
    int re=n;
    for(int i=2;i*i<=n;++i)if(n%i==0){
        re=re/i*(i-1);
        while(n%i==0) n/=i;
    }
    if(n>1) re=re/n*(n-1);
    return re;
}
void Polya(){
    int n=read<int>(),ans=0;
    for(int i=1;i*i<=n;++i)if(n%i==0){
        ans=add(ans,mul(phi(i),fpow(n,n/i-1)));
        if(i*i!=n) ans=add(ans,mul(phi(n/i),fpow(n,i-1)));
    }
    printf("%d\n",ans);
}
int main(){
//  freopen("LG4980.in","r",stdin),freopen("LG4980.out","w",stdout);
    for(int t=read<int>();t--;) Polya();
    return 0;
}