Skip to main content

Pólya 计数

参考资料​

例题​

洛谷 P4980 【模板】Pólya 定理

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

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

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int mod=1e9+7;
ll Pow(ll a,ll b)
{
	a%=mod;
	ll res=1;
	while(b)
	{
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
ll phi(ll n)
{
	ll res=n;
	for(ll i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			res=res/i*(i-1);
			while(n%i==0)n/=i;
		}
	}
	if(n>1)res=res/n*(n-1);
	return res;
}
ll polya(ll n,ll m)
{
	ll res=0;
	for(int i=1;i*i<=m;i++)
	{
		if(m%i)continue;
		res=(res+phi(i)*Pow(n,m/i-1)%mod)%mod;
		if(i*i!=n)res=(res+phi(n/i)*Pow(n,i-1)%mod)%mod;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		cout<<polya(n,n)<<'\n';
	}
	return 0;
}