BZOJ 1004 【HNOI2008】 Cards

题目链接：Cards

　　听说这道题是染色问题的入门题，于是就去学了一下\(Burnside\)引理和\(P\acute{o}lya\)定理(其实还是没有懂)，回来写这道题。

　　由于题目中保证"任意多次洗牌都可用这\(m\)种洗牌法中的一种代替"，于是有了封闭性。

　　结合律显然成立。

　　题目中还保证了"对每种洗牌法，都存在一种洗牌法使得能回到原状态"，逆元也有了。

　　只剩下一个单位元，我们手动补上。单位元就是不洗牌。

　　所以所有的洗牌方案构成了一个置换群。于是就可以用$Burnside$引理了。

　　这道题由于颜色有数目限制，那么就不能直接上$P\acute{o}lya$定理了。

　　根据$Burnside$引理，本质不同的染色数目$ans$就是$C(f)$的平均数。于是我们可以暴力算出$C(f)$，由于是在模意义下，所以除法变为逆元。

　　当然，这里的暴力方法不是指指数级的枚举，而是$dp$。因为一种方案要在一个置换下本质不变，那么在同一个循环内的位置颜色必定相等。于是把所有循环都抠出来然后暴力三维背包就可以了。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define N 61

using namespace std;

typedef long long llg;

int Sr,Sb,Sg,m,p,ans;

int nt[N],siz[N],n,f[N][N][N];

bool vis[N];

void gi(int &x){if(x>=p) x%=p;}

int mi(int a,int b){

	int s=1;

	while(b){

		if(b&1) s=s*a,gi(s);

		a=a*a,gi(a); b>>=1;

	}

	return s;

}

int work(){

	int tol=0;

	for(int i=1;i<=n;i++) vis[i]=0;

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

		if(!vis[i]){

			siz[++tol]=0;

			for(int j=i;!vis[j];j=nt[j]) vis[j]=1,siz[tol]++;

		}

	for(int r=0;r<=Sr;r++)

		for(int b=0;b<=Sb;b++)

			for(int g=0;g<=Sg;g++)

				f[r][b][g]=0;

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

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

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

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

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

					if(r>=siz[i]) f[r][b][g]+=f[r-siz[i]][b][g];

					if(b>=siz[i]) f[r][b][g]+=f[r][b-siz[i]][g];

					if(g>=siz[i]) f[r][b][g]+=f[r][b][g-siz[i]];

					gi(f[r][b][g]);

				}

	return f[Sr][Sb][Sg];

}

int main(){

	File("a");

	scanf("%d %d %d %d %d",&Sr,&Sb,&Sg,&m,&p);

	n=Sr+Sb+Sg;

	for(int i=1;i<=n;i++) nt[i]=i; ans=work();

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

		for(int j=1;j<=n;j++) scanf("%d",&nt[j]);

		ans+=work(); gi(ans);

	}

	ans*=mi(m+1,p-2); gi(ans);

	printf("%d",ans);

	return 0;

}