首页 > 代码库 > 【bzoj1004】 HNOI2008—Cards

【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;}

 

【bzoj1004】 HNOI2008—Cards