Pólya 计数

参考资料

• Pólya 计数 - OI Wiki

例题

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

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

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

代码（1）

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=100005;
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 sum=0;
	for(int i=1;i*i<=m;i++)
	{
		if(m%i==0)
		{
			sum=(sum+phi(i)*Pow(n,m/i-1)%mod)%mod;
			if(i*i!=n)sum=(sum+phi(n/i)*Pow(n,i-1)%mod)%mod;
		}
	}
	return sum;
}
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;
}