bzoj1004 [HNOI2008] Cards

题意:书桌上的N张牌,要求染出Sr张红色,Sb张蓝色,Sg张绿色,M种不同的洗牌法,两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种。保证任意多次洗牌都可用这 m种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。问有多少种不同的染色方案(对一个数取模)

经过洗牌的序列是等价的,并且题目保证了洗牌具有传递性,对称和自反的性质,统计不等价的染色方法可以用$Burnside$引理来实现。对于每种洗牌法$i$(不洗牌,即每张牌在原位也是一种洗牌(第$m+1$种洗牌),因为要保证任意多次某种洗牌可以被一种方法取代,这样就会有归到原位的情况),求经过这次洗牌序列颜色不变的数目$C_i$,那么不等价的染色方法就有$\frac{1}{m+1}\sum_{i=1}^{m+1} C_i$。

对于不在原位的洗牌方法可以把洗牌的序列拆成循环,因为要保证洗牌后序列不变,所以每个循环内的颜色应该相同。一共只有三种颜色,所以可以直接用三维背包完成。对于所有牌在原位的序列,直接全排列即可,有$\frac{n!}{S_r\cdot S_b \cdot S_g}$种方法。

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=65;
int dp[maxn][maxn][maxn][maxn];
int a[4],n,xp[maxn][maxn],m,P,tot=0,C[maxn];
bool vis[maxn];
vector<int > loop[maxn];
int quickpow(int x,int k)
{
int ret=1;
while(k) {
if(k&1) ret=ret*x%P;
x=x*x%P;
k>>=1;
}
return ret;
}
int facto(int x)
{
int ret=1;
for(int i=1;i<=x;i++) ret=1ll*ret*i%P;
return ret;
}
int main()
{
for(int i=1;i<=3;i++) scanf("%d",&a[i]);
n=a[1]+a[2]+a[3];
int tmp=0,st=0,siz=0;
scanf("%d%d",&m,&P);
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) scanf("%d",&xp[i][j]);
memset(dp,0,sizeof(dp));
dp[0][0][0][0]=1;
tot=0;
memset(vis,0,sizeof(vis));
for(int j=1;j<=n;j++) {
if(vis[j]) continue;
if(xp[i][j]!=j) {
loop[++tot].push_back(j);
vis[j]=true;
tmp=j;st=j;
while(xp[i][tmp]!=st) {
loop[tot].push_back(xp[i][tmp]);
vis[xp[i][tmp]]=true;
tmp=xp[i][tmp];
}
}else loop[++tot].push_back(j);
}
for(int j=1;j<=tot;j++) {
siz=(int)loop[j].size();
for(int k=0;k<=a[1];k++) {
for(int l=0;l<=a[2];l++) {
for(int o=0;o<=a[3];o++) {
if(k>=siz) dp[j][k][l][o]=(dp[j][k][l][o]+dp[j-1][k-siz][l][o])%P;
if(l>=siz) dp[j][k][l][o]=(dp[j][k][l][o]+dp[j-1][k][l-siz][o])%P;
if(o>=siz) dp[j][k][l][o]=(dp[j][k][l][o]+dp[j-1][k][l][o-siz])%P;
}
}
}
}
C[i]=dp[tot][a[1]][a[2]][a[3]];
for(int j=1;j<=tot;j++) loop[j].clear();
}
int inv=quickpow(m+1,P-2),ans=0,ad=facto(n);
for(int i=1;i<=m;i++) ans=(ans+C[i])%P;
for(int i=1;i<=3;i++) ad=1ll*ad*quickpow(facto(a[i]),P-2)%P;
ans=(ans+ad)%P;
ans=ans*inv%P;
printf("%d\n",ans);
return 0;
}