BZOJ 1004 Cards

发表于 | 更新于

Link

Wiki上说Burnside引理的公式最早是柯西发现的？让我想起了阿拉伯数字有木有

Solution

部分来自NoAlGo

群

一个集合GG，在GG上定义了二元运算∗*满足以下条件

  1. 封闭性，即任意a∈G,b∈Ga\in G,b\in G,有a∗b∈Ga*b\in G。
  2. 结合律，(a∗b)∗c=a∗(b∗c)(a*b)*c=a*(b*c)。
  3. 存在单位元ee。对任意a∈Ga\in G，a∗e=e∗a=aa*e=e*a=a。
  4. 存在逆元。对任意元素aa，存在bb，使得a∗b=b∗a=ea*b=b*a=e。

则称GG是对于运算∗*的群。

Burnside引理

GG是 上的置换群， ，记f(ai)f(a_i)为置换aia_i的不动点个数，则GG在XX上的不同染色方案数目为 1∣G∣∑f(ai)\dfrac {1}{|G|}\sum f(a_i)

然后看题目

  1. 保证任意多次洗牌都可用这 m种洗牌法中的一种代替
  2. 对每种洗牌法，都存在一种洗牌法使得能回到原状态

就满足了群的条件1,2,4，还有一个条件3需要满足，那就添加一个置换am+1={bi,bi=i}a_{m+1}=\{b_i,b_i=i\}

然后就可以上Burnside引理了。

Tips

用各种定理都要牢记适用条件，不能只记结论随便用。比如古代猪文。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
const int MAXB=25,MAXN=MAXB*3;
int P;
int Pow(int base,int v,int P)
{
	int res=1;
	while(v)
	{
		if(v&1)
			(res*=base)%=P;	
		(base*=base)%=P;
		v>>=1;
	}
	return res;
}
int inv(int a,int P)
{
	return Pow(a,P-2,P);
}
int Calc(int *a,int n,int R,int B,int G)
{
	static int cyc[MAXN],cc;
	static bool ud[MAXN];
	cc=0;
	memset(ud,0,sizeof(ud));
	for(int i=1;i<=n;++i)
	{
		if(ud[i]) continue;
		int l=0;
		while(!ud[i])
		{
			l++;
			ud[i]=1;
			i=a[i];
		}
		cyc[++cc]=l;
	}
	//用x个体积为v_i的物品 填3个给定大小的背包的方案数目
	static int f[MAXN][MAXB][MAXB][MAXB];
	memset(f,0,sizeof(f));
	f[0][0][0][0]=1;
	for(int i=1;i<=cc;++i)
		for(int r=0;r<=R;++r)
			for(int b=0;b<=B;++b)
				for(int g=0;g<=G;++g)
				{
					if(cyc[i]<=r)
						(f[i][r][b][g]+=f[i-1][r-cyc[i]][b][g])%=P;
					if(cyc[i]<=b)
						(f[i][r][b][g]+=f[i-1][r][b-cyc[i]][g])%=P;
					if(cyc[i]<=g)
						(f[i][r][b][g]+=f[i-1][r][b][g-cyc[i]])%=P;
				}
	return f[n][R][B][G];
}
int main()
{
	static int a[MAXN];
	int R,B,G,m;
	get(R),get(B),get(G),get(m),get(P);
	int n=R+B+G;
	for(int i=1;i<=n;++i)
		a[i]=i;
	int Ans=Calc(a,n,R,B,G);
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=n;++j) get(a[j]);	
		(Ans+=Calc(a,n,R,B,G))%=P;
	}
	(Ans*=inv(m+1,P))%=P;
	put(Ans),putchar('\n');
	return 0;
}