Prutekoi's blog

burnside引理和Polya定理用于解决一些染色本质不同状态的计数问题。
例题:

给定一个$n$个点，$n$条边的环，有$n$种颜色，给每个顶点染色，问有多少种本质不同的染色方案,本质不同定义为：只需要不能通过旋转与别的染色方案相同。

我们发现这个本质不同可以有一个更数学一点的定义,即:

有一些置换,若一个状态可以通过其中一个置换到达另一个状态,则这两个状态本质相同。

burnside引理:

对于一个置换$f$,若一个染色方案$S$经过置换后不变，称$S$为$f$的不动点。将$f$的不动点数目记为$C(f)$，则可以证明等价类数目为所有$C(f)$的平均值。

那么对于这道题来说,有$n$个置换,分别对应着顺时针转$1-n$个。只需要枚举所有的$n$个置换,再枚举$n^n$种状态,计算$C(f)$,套用公式即可。
...
太不优秀啦!!
于是我们有了Polya定理:

对于一个置换$f$,若他可以拆成$k$个简单环,且颜色数为$m$,则$C(f)=m^k$。

这个也很好理解。对于置换f的每个环,环内部的颜色都要是相同的,才能成为不动点。于是乘法原理一下就好啦。

于是上面那道例题,可以证明旋转$k$次的置换环的个数为$gcd(k,n)$,他就成为一道很水的莫反题啦,完结撒花!

其实抛开染色的话好像可以更好地理解：我们枚举每个置换之后，就是加了一个限制条件：每个环内部都必须是一致的。而其他的条件是一样的。
比如无标号环的计数的结论：

给定一类组合对象 $A$，由 $k$ 个 $A$ 中元素组成的环的OGF应当是

$\frac{1}{k}\sum_{0\leq i<k}A(x^{k/\gcd(i,k)})^{\gcd(i,k)}=\frac{1}{k}\sum_{d|k}\varphi(d)A(x^d)^{k/d}$

这其中的道理是因为我们固定了环内部一致后，这个环就是一个整体了，所以是 $x^{k/\gcd(i,k)}$。
还有，若这个染色是有一些限制的，比如一道考试题：

给一个长度为 $n$ 的环黑白染色，要求两个白珠子的距离不得小于 $k$，求本质不同方案数。（只算旋转不算翻转）

我们套用polya定理后，是相当于多了一个循环节的限制。因为循环节之间也是首尾相接，那么我们可以把一个循环节看成一个环，在这个环内两个白珠子的距离不得小于 $k$，这样就满足条件了。这时没有了本质不同的限制，我们直接运用组合数学的知识解决即可。

证明 什么的就先咕着了

关于burnside引理，我们究竟应该把置换作用在谁身上？大概就是如果题目的定义是“对于由元素A构成的元素B，如果存在对两个元素B中的元素A编号的方式，使得两个元素B中的所有元素一一对应，那么两个元素B是同构的”，那么就要考虑对元素A应用polya定理。比如图同构中同构的定义是两张图（元素B）存在对点（元素A）标号的方式，使得两张图的点集和边集（所有元素）一一对应，那么两张图同构。

在图同构中，我们考虑点的置换，那么边就像是点的“颜色”一样。图中有这条边是一种颜色，没有就是另一种颜色。找到染色方案（连边方案）对于置换的不动点即可。如果边的两个端点在同一个轮换中，那么它的等价类就是与它在同一个轮换中，且两端点在轮换中的距离与它相等的边。于是这种类型的等价类就是 $\sum a_i/2$，其中 $a_i$ 是每个轮换的长度。而对于跨越两个轮换的边（长度分别为 $x,y$），考虑不停地作用置换，它会在 $lcm(x,y)$ 次后回到原位。而两轮换间的边总共有 $xy$ 条，于是等价类个数就是 $\frac{xy}{lcm(x,y)}=\gcd(x,y)$。计算出边的等价类个数 $c$ 之后只需满足同一等价类中的边要选都选。于是不动点个数就是 $2^c$。对于所有置换加起来最后除以 $n!$ 即可。而发现等价类个数只与每个轮换的大小有关，于是可以枚举整数划分，可以在一秒内跑出 $67$，跑出 $100$ 需要89秒...

#include<bits/stdc++.h>
using namespace std;
const int N=120,mod=997;
int n,ans,J[N],inv[N],I[N],a[N],m,g[N][N],mx,pw[N*N],dat,kk;
void solve(){
	int num=J[n],ret=0;kk++;
	for(int i=1,j;i<=m;i++){
		j=i;num=1ll*num*inv[a[i]]%mod;
		while(j<m&&a[j+1]==a[i])num=1ll*num*inv[a[++j]]%mod;
		num=1ll*num*I[j-i+1]%mod;i=j;
	}
	for(int i=1;i<=m;i++){
		ret+=a[i]/2;
		for(int j=i+1;j<=m;j++)ret+=g[a[i]][a[j]];
	}
	ans=(ans+1ll*num*pw[ret])%mod;
}
void dfs(int x,int y){
	if(!x){solve();return;}
	for(int i=min(x,y);i;i--)
		a[++m]=i,dfs(x-i,i),m--;
}
int main(){
	scanf("%d",&n);J[0]=I[0]=inv[1]=pw[0]=1;
	for(int i=1;i<=n*n;i++)pw[i]=pw[i-1]*2%mod;
	for(int i=2;i<=n;i++)inv[i]=mod-1ll*mod/i*inv[mod%i]%mod;
	for(int i=1;i<=n;i++)J[i]=1ll*J[i-1]*i%mod,I[i]=1ll*I[i-1]*inv[i]%mod;
	for(int i=0;i<=n;i++)g[i][0]=g[0][i]=i;
	for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)g[j][i]=g[i][j]=g[j][i%j];
	dfs(n,n);cout<<1ll*ans*I[n]%mod;
	return 0;
}

而据说图同构已经准线性算法了...即 $2^{polylog(n)}$。咱也不知道上面这个做法是啥复杂度2333，反正我觉得挺优秀了。