lp4980 【模板】Polya定理

Polya定理是一个关于置换群中组合计数的定理。
首先我们来了解Burnside引理。这个引理的证明较为复杂,在这里仅介绍其内容。
Burnside引理的内容是这样的:在置换意义下本质不同的染色方案数,等于单个置换不会改变的染色方案数的平均值。
那么,单个置换不会改变的染色方案数要怎么求呢?我们不妨把置换关系建成一张图,那么这张图必然由若干个环构成。也就是说,对于同一种置换,可能存在若干个环,而每个初始状态就是环上的一个节点。Polya定理描述的就是,某一种置换不会改变的方案数,等于颜色数的「这个置换对应的循环节个数」

阐述了上述两个定理,现在我们来看这一题。
我们观察到,这个环上存在 n 种置换。对于置换 i 而言,它的循环大小是:
$$
\frac{n}{\gcd(n,i)}
$$
这也就意味着,它的循环个数是:
$$
\gcd(n,i)
$$
那么我们要求的答案就是:
$$
\frac{\sum_{i=1}^nn^{(n,i)}}{n}
$$
然而这样计算答案的复杂度是 O(n) 的,我们无法接受。
我们不妨考虑枚举这个公因子。那么,容易证明的是,每一个公因子d对应的置换个数是\(\varphi(\frac{n}{d})\)

这是因为, d 是 \(\frac{n}{d}\) 个数的因数,而这些数中,如果它和\(\frac{n}{d}\)存在公因子的话,那么它和n的最大公因数必然大于d。

所以,我们求的就是:
$$
\frac{\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}}}{n}=\sum_{d|n}\varphi(\frac{n}{d})n^{\frac{n}{d}-1}
$$
我们只要枚举n的因数即可。

然而求这里的 \(\varphi\) 倒可能存在一些问题。事实上,由于我们要取的因数的值域是 \(10^9\) ,我们无法使用欧拉筛来预处理,而需要现场做。

这样的复杂度是不是对的呢?它的最坏情况是 \(O(Tn^{\frac{3}{4}})\) 的,但由于我并不会分析的一些性质,它不会达到这个值。因此可以通过此题。

另:括号忘记加,爆O泪两行。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const int N=1000005;
inline ll pw(ll A,ll X){
	ll RT=1;
	while(X){
		if(X&1){
			RT*=A;RT%=MOD;
		}
		A*=A;A%=MOD,X>>=1;
	}
	return RT;
}
int n;
inline int phi(int X){
	int RT=1;
	for(int i=2;i*i<=X;++i){
		if(X%i==0){
			X/=i;RT*=i-1;
			while(X%i==0){
				X/=i;RT*=i;
			}
		}
		if(X==1){
			break;
		} 
	}
	if(X>1){
		RT*=X-1;
	}
	return RT;
}
void init(){
	scanf("%d",&n);
	ll ans=0;
	for(int i=1;i*i<=n;++i){
		if(n%i==0){
			ans+=(1ll*phi(n/i)*pw(n,i-1))%MOD;
			if(i*i!=n){
				ans+=(1ll*phi(i)*pw(n,n/i-1))%MOD;
			}
			ans%=MOD;
//			printf("%d %lld\n",i,ans);
		}
	}
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}