BZOJ 1004 HNOI2008 Cards Burnside引理-白红宇

BZOJ 1004 HNOI2008 Cards Burnside引理

阅读量：5742 次

发布时间：2019-06-18

本文共 1310 字，大约阅读时间需要 4 分钟。

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

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

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

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

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

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

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

#include
     
      #include
      
       #include
       
        #include
        
         #define M 70using 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<
         
          <