bzoj1004: [HNOI2008]Cards

題目

#1.Burnside引理

Burnside引理與Polya定理

題解

//d[i]表示第i個循環的長度，b[i]是标記
#include<bits/stdc++.h>
using namespace std;
int f[22][22][22],i,b[62],a[62][62],n,m,ans,sr,sb,sg,M,x,d[62],j,y;
int dp(int x){
	memset(b,0,sizeof(b));
	int sum=0,p;
	for (int i=1;i<=n;i++)
		if (!b[i]){
			d[++sum]=0;
			for (p=i;!b[p];p=a[x][p]) d[sum]++,b[p]=1;
		}
	memset(f,0,sizeof(f));
	f[0][0][0]=1;
//剛開始把下面三個循環改成>=d[h]，想省略三個判斷，但事實上不能這麼做
	for (int h=1;h<=sum;h++)
		for (int i=sr;i>=0;i--)
			for (int j=sb;j>=0;j--)
				for (int k=sg;k>=0;k--){
					if (i>=d[h]) f[i][j][k]=(f[i][j][k]+f[i-d[h]][j][k])%M;
					if (j>=d[h]) f[i][j][k]=(f[i][j][k]+f[i][j-d[h]][k])%M;
					if (k>=d[h]) f[i][j][k]=(f[i][j][k]+f[i][j][k-d[h]])%M;
				}
	return f[sr][sb][sg];
}
void ex_gcd(int a,int b,int &x,int &y){
	if (!b){
		x=1;y=0;
		return;
	}
	ex_gcd(b,a%b,y,x);
	y-=a/b*x;
}
int main(){
	scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&M);
	n=sr+sb+sg;
	for (i=1;i<=m;i++)
		for (j=1;j<=n;j++) scanf("%d",&a[i][j]);
	m++;
	for (i=1;i<=n;i++) a[m][i]=i;
	for (i=1;i<=m;i++) ans=(ans+dp(i))%M;
	ex_gcd(m,M,x,y);
	x=(x+M)%M;
	printf("%d",ans*x%M);
}
           

#2.組合數學

題解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans,n,sr,sb,sg,m,M,i;
ll t;
int pm(int x,int y){
	int z=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1) z=z*x%M;
	return z;
}
int main(){
	scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&M);
	n=sr+sb;
	for (i=t=1;i<=sr;i++) t=t*(n-i+1)/i;//剛開始習慣性寫成*=，好傻逼
	ans=t%M;
	n+=sg;
	for (i=t=1;i<=sg;i++) t=t*(n-i+1)/i;
	ans=t%M*ans%M;
	printf("%d",ans*pm(m+1,M-2)%M);
}
           

注：本題因為模數是質數，是以費馬小定理和exgcd都可以求逆元