BZOJ1004 [HNOI2008]Cards（置換群+dp）

用到了置換群Burnside引理：

等價類數目 = average( C(fi) )，其中C(fi):對于置換fi的"不動點"的數目(不動點：若将所有元素染色，經fi置換後顔色不變的一組方案)

【題解】

将置換fi分解為循環後，由于各循環獨立，我們可以發現：若将所有元素染色，對于fi的不動點，每個循環内部所有元素顔色相同 

對于每個fi求不動點數目，用dp：

F[i][j][k]表示：前i個循環中，紅色有j個，藍色有k個的方案數 

狀态轉移：讨論第i個循環塗什麼顔色就行了 

注意："不洗牌"也是一種情況對應置換(1 2 …n)，是以置換共有m+1個 

具體流程我在代碼注釋中已經寫得很清楚了

#include<stdio.h>
#include<stdlib.h>
int cha[100]={0},f[100][100][100]={0},vis[100]={0},xh[100]={0};//cha[]:洗牌方式, xh[]:cha[]分解成的循環節長度 
int mod;
void gcd(int a,int b,int& d,int& x,int& y)
{
	int t;
	if(b==0)
	{
		d=a;
		x=1;
		y=0;
		return;
	}
	gcd(b,a%b,d,x,y);
	t=x;
	x=y;
	y=t-a/b*y;
}
int ni(int a,int n)
{
	int d,x,y;
	gcd(a,n,d,x,y);
	return (x+n)%n;
}
int main()
{
	int Sr,Sb,Sg,n,m,i,j,k,l,p,ans=0;//p代表xh[]的位數，不是mod! 
	scanf("%d%d%d%d%d",&Sr,&Sb,&Sg,&m,&mod);
	m++;//"不洗牌"也算作一種方案 
	n=Sr+Sb+Sg;
	for(l=1;l<=m;l++)
	{
		for(i=1;i<=n;i++)
		{
			if(l==1) cha[i]=i;
			else scanf("%d",&cha[i]);
			vis[i]=0;
		}
		p=0;//分解為循環節 
		for(i=1;i<=n;i++)
			if(vis[i]==0)
			{
				j=i;
				xh[++p]=0;
				do
				{
					vis[j]=1;
					xh[p]++;
					j=cha[j];
				}
				while(j!=i);
			}//接下來統計不動點的個數：
		for(i=0;i<=p;i++)
			for(j=0;j<=Sr;j++)
				for(k=0;k<=Sb;k++)
					f[i][j][k]=0;
		f[0][0][0]=1;//三維背包的邊界 
		for(i=1;i<=p;i++)
			for(j=0;j<=Sr;j++)
				for(k=0;k<=Sb;k++)
				{
					if(j+k>i) break;
					if(i-j-k>Sg) continue;
					if(j>=xh[i]) f[i][j][k]+=f[i-1][j-xh[i]][k];
					if(k>=xh[i]) f[i][j][k]+=f[i-1][j][k-xh[i]];
					if(i-j-k>=xh[i]) f[i][j][k]+=f[i-1][j][k];
					f[i][j][k]%=mod;
				}
		ans+=f[p][Sr][Sb];
	}
	ans=(ans*ni(m,mod))%mod;
	printf("%d",ans);
	return 0;
}