【bzoj1004】 HNOI2008—Cards

http://www.lydsy.com/JudgeOnline/problem.php?id=1004 (题目链接)

题意

　　n张卡片，染成3种颜色，每种颜色只能染固定张数。给出一些洗牌方案，问染色方案数。

Solution

　　Burnside引理。

　　左转题解：LCF

代码

// bzoj1004

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 1<<30

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=100;

LL f[maxn][maxn][maxn],a[maxn],vis[maxn],size[maxn];

LL n,m,P,R,G,B;

LL power(LL a,LL b) {

	LL res=1;

	while (b) {

		if (b&1) res=res*a%P;

		a=a*a%P;b>>=1;

	}

	return res;

}

LL dp() {

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

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

	int cnt=0;

	for (int i=1;i<=n;i++) if (!vis[i]) {

			size[++cnt]=0;

			for (int j=a[i];!vis[j];j=a[j]) vis[j]=1,size[cnt]++;

		}

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

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

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

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

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

					if (r>=size[i]) f[r][b][g]=(f[r][b][g]+f[r-size[i]][b][g])%P;

					if (b>=size[i]) f[r][b][g]=(f[r][b][g]+f[r][b-size[i]][g])%P;

					if (g>=size[i]) f[r][b][g]=(f[r][b][g]+f[r][b][g-size[i]])%P;

				}

	return f[R][B][G]%P;

}

int main() {

	scanf("%lld%lld%lld%lld%lld",&R,&B,&G,&m,&P);

	n=R+B+G;LL ans=0;

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

	ans=(ans+dp())%P;

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

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

		ans=(ans+dp())%P;

	}

	ans*=power(m+1,P-2);

	printf("%lld",ans%P);

	return 0;

}