burnside引理&polya定理

参考资料：

《polya计数法的应用》--陈瑜希

黄学长

置换：
置换即是将n个元素的染色进行交换，产生一个新的染色方案。
群：
一个元素的集合G与一个二元运算(*)构成一个群。群满足以下性质：
1. 封闭性：\(\forall a,b \in G,\exists c\in G ,c=a*b\)
2. 结合律：\(\forall a,b,c,(a*b)*c=a*(b*c)\)
3. 单位元：\(\exists e\in G,\forall a,a*e=e*a=a\)
4. 逆元：\(\forall a\in G,\exists b\in G,a*b=b*a=e,b=a^{-1}\)
置换群：
即对于置换的集合的群，其中的二元运算为置换的连接，即对一个染色方案置换后的方案进行置换。
burnside引理：
burnside引理用来求在一个置换群的置换集合下本质不同的染色方案数，公式为
\[L=\frac{1}{|G|}\sum_j D(a_j)
\]
其中，L表示本质不同的染色方案数，|G|表示置换个数，\(D(a_j)\)表示在\(a_j\)置换下不变的染色方案数。
证明的话，有兴趣的可以自己看看论文，反正我不会证。。。
polya定理：
使用burnside引理时，需要求出在某一个置换下不变的染色方案数，而在某些情况下，这种东西并不好求。
循环：在一个置换中，形成的一个环的结构，称为循环。一个置换中的循环数称为循环节数。
当有m种颜色时，\(D(a_j)=m^{cj}\)其中，\(c_j\)为置换的循环节数。

例题：

bzoj1004

题意为给出一个置换群，有三种颜色，每种颜色有数量限制，求本质不同的染色方案。

首先枚举每个置换。对于一个置换，在该置换下不变的元素在循环处颜色一定相同。找到该置换下的循环，做三维背包即可。

程序参考自hzwer

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int Maxn=70;

int vis[Maxn],n,p,a[Maxn][Maxn],f[Maxn][Maxn][Maxn];

int r,b,g,siz[Maxn],m,ans;

int powp(int a,int b,int mod) {

	int ans=1;

	while(b) {

		if(b&1) ans=ans*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return ans;

}

int dp(int x) {

	int cnt=0;

	memset(vis,0,sizeof(vis));

	for(int i=1;i<=n;i++)

		if(vis[i]==0) {

			vis[i]=1;

			cnt++;

			siz[cnt]=1;

			int p=i;

			while(vis[a[x][p]]==0) {

				siz[cnt]++;

				p=a[x][p];

				vis[p]=1;

			}

		}

	memset(f,0,sizeof(f));

	f[0][0][0]=1;

	for(int o=1;o<=cnt;o++)

		for(int i=r;i>=0;i--)

			for(int j=b;j>=0;j--)

				for(int k=g;k>=0;k--) {

					if(i>=siz[o]) f[i][j][k]=(f[i][j][k]+f[i-siz[o]][j][k])%p;

					if(j>=siz[o]) f[i][j][k]=(f[i][j][k]+f[i][j-siz[o]][k])%p;

					if(k>=siz[o]) f[i][j][k]=(f[i][j][k]+f[i][j][k-siz[o]])%p;

				}

	return f[r][b][g];

}

int main() {

	scanf("%d%d%d%d%d",&r,&b,&g,&m,&p);

	n=r+b+g;

	for(int i=1;i<=m;i++)

		for(int j=1;j<=n;j++)

			scanf("%d",&a[i][j]);

	m++;

	for(int i=1;i<=n;i++) a[m][i]=i;

	for(int i=1;i<=m;i++) ans+=dp(i);

	printf("%d\n",ans%p*powp(m,p-2,p)%p);

	return 0;

}

Burnside引理

burnside引理&polya定理

burnside引理&polya定理

参考资料：

例题：

bzoj1004