burnside引理&polya定理


参考资料:

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

黄学长


  1. 置换:

    置换即是将n个元素的染色进行交换,产生一个新的染色方案。

  2. 群:

    一个元素的集合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}\)

  3. 置换群:

    即对于置换的集合的群,其中的二元运算为置换的连接,即对一个染色方案置换后的方案进行置换。

  4. burnside引理:

    burnside引理用来求在一个置换群的置换集合下本质不同的染色方案数,公式为

    \[L=\frac{1}{|G|}\sum_j D(a_j)
    \]

    其中,L表示本质不同的染色方案数,|G|表示置换个数,\(D(a_j)\)表示在\(a_j\)置换下不变的染色方案数。

    证明的话,有兴趣的可以自己看看论文,反正我不会证。。。

  5. 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;
}
05-11 11:36