P4980 【模板】Polya定理

发表于 | 评论数： | 阅读次数：
本文字数： 3.3k | 阅读时长 ≈ 3 分钟

P4980 【模板】Polya定理

传送门

洛谷

题目描述

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

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

5
1
2
3
4
5

输出样例#1：

1
3
11
70
629

说明

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

分析

$Burnside$引理

对于每个置换$g$，我们定义$C(g)$为在置换$g$下保持不变的方案数。
则有： 本质不同的方案数为$C(g)$的平均数。
即：

证明需要用到群论，本蒟蒻不是很会，就不现丑了。

$Polya$定理

$Polya$定理其实是对$Burnside$引理的具体化，提供了计算不动点的具体方法。
由于$Burnside$引理每次需要枚举状态，显然无法让人接受。
于是，$Polya$定理出现了。
假设一个置换有$k$个循环，易知每个循环对应的所有位置颜色需一致，而任意两个循环之间选什么颜色互不影响。因此，如果有$m$种可选颜色，则该置换对应的不动点个数为$m^k$。用其替换$Burnside$引理中的$C(g)$，即$C(g)=m^k$。得到等价类数目为：

其中$\left | G \right |$表示置换的数目，$k_i$表示第$i$个置换包含的循环个数。

本题

考虑第$i$次旋转。
显然一个的循环节长度是$\frac{lcm(n,i)}{i}$，形象的，想象你有一条长$i$的线段用来倍长，因为我们总长为$n$，所以倍长后的结果一定被$n$整除，那我们就将干脆设最终的长度的$lcm(n,i)$，而我们每次只能从一条长$i$的线段中取一个放入我们的循环中，那么我们的循环自然为$\frac{lcm(n,i)}{i}$。
既然每个循环节长度是$\frac{lcm(n,i)}{i}$，我们有$n$个数放入循环节中，那么循环节个数就是$\frac{n}{\frac{lcm(n,i)}{i}}$，即$gcd(n,i)$。
所以：

再向式子中带入本题变量，得：

但这样是过不了的，我们还要优化一波。

其中$\varphi$为欧拉函数，我们可以在$O(\sqrt n)$的时间内求出。

参考资料

$Burnside$引理 & $Polya$定理

QAQqwe的 Burnside引理与Polya定理
TenderRun的我对Burnside定理的理解
周道-Althen的 超低能解读群论

本题

SLF_LLL_SPFA的洛谷题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define p 1000000007
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
	read(b...);
}
int T,n;
int fpow(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)ans=(1ll*ans*x)%p;
		x=(1ll*x*x)%p;
		y>>=1;
	}
	return ans;
}
int phi(int x)
{
	int ans=x;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			ans=ans/i*(i-1);
			while(x%i==0)x/=i;
		}
	}
	if(x!=1)ans=ans/x*(x-1);
	return ans%p;
}
int main()
{
	T=read<int>();
	for(int tot=1;tot<=T;tot++)
	{
		n=read<int>();
		int ans=0;
		for(int i=1;i*i<=n;i++)
			if(n%i==0)
			{
				ans=(ans+(1ll*fpow(n,i)*phi(n/i))%p)%p;
				if(n/i!=i)ans=(ans+(1ll*fpow(n,n/i)*phi(i))%p)%p;
			}
		ans=(1ll*ans*fpow(n,p-2))%p;
		printf("%d\n",ans);
	}
    return 0;
}