BZOJ 1004 HNOI2008 Cards Burnside引理

标题效果：特定n张卡m换人，编号寻求等价类

数据保证这m换人加上置换群置换后本身构成

BZOJ坑爹0.0 条件不那么重要出来尼玛怎么做

Burnside引理……昨晚为了做这题硬啃了一晚上白书0.0 都快啃吐了0.0

Burnside引理：一个置换群下的等价类个数等于全部置换的不动点个数的平均值

没有接触过群论的建议去啃白书…… 网上的东西看不懂的

最后那个除法要用乘法逆元 我懒得写EXGCD写了费马小定理0.0

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 70

using namespace std;

int r,g,b,m,n,p,ans;

int a[M],stack[M],top;

int f[21][21][21];

void DFS(int x)

{

	stack[top]++;

	int temp=a[x];

	a[x]=0;

	if(a[temp])

		DFS(temp);

}

int DP()

{

	int i,j,k;

	memset(f,0,sizeof f);f[0][0][0]=1;

	while(top)

	{

		for(i=r;~i;i--)

			for(j=g;~j;j--)

				for(k=b;~k;k--)

				{

					if(i>=stack[top]) f[i][j][k]+=f[i-stack[top]][j][k];

					if(j>=stack[top]) f[i][j][k]+=f[i][j-stack[top]][k];

					if(k>=stack[top]) f[i][j][k]+=f[i][j][k-stack[top]];

					f[i][j][k]%=p;

				}

		stack[top--]=0;

	}

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

}

int KSM(int x,int y)

{

	int re=1;

	while(y)

	{

		if(y&1)re*=x,re%=p;

		x*=x,x%=p;

		y>>=1;

	}

	return re;

}

int main()

{

	int i,j;

	cin>>r>>g>>b>>m>>p;

	n=r+g+b;

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

	{

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

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

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

			if(a[j])

				++top,DFS(j);

		ans+=DP(),ans%=p;

	}

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

		a[j]=j;

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

		if(a[j])

			++top,DFS(j);

	ans+=DP(),ans%=p;

	ans*=KSM(m+1,p-2),ans%=p;

	cout<<ans<<endl;

}

版权声明：本文博客原创文章，博客，未经同意，不得转载。

BZOJ 1004 HNOI2008 Cards Burnside引理的相关教程结束。