首页 > 代码库 > [BZOJ1004](HNOI 2008) Cards
[BZOJ1004](HNOI 2008) Cards
Description
小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目 前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝 色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌 法,而每种方法可以使用多次)洗成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).
Input
第一行输入 5 个整数：Sr,Sb,Sg,m,p(m<=60,m+1<p<100)。n=Sr+Sb+Sg。接下来 m 行，每行描述
一种洗牌法，每行有 n 个用空格隔开的整数 X1X2...Xn，恰为 1 到 n 的一个排列，表示使用这种洗牌法，
第 i位变为原来的 Xi位的牌。输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替，且对每种
洗牌法，都存在一种洗牌法使得能回到原状态。
Output
不同染法除以P的余数
Sample Input
2 3 1
3 1 2
Sample Output
HINT
有2 种本质上不同的染色法RGB 和RBG，使用洗牌法231 一次可得GBR 和BGR，使用洗牌法312 一次 可得BRG 和GRB。100%数据满足 Max{Sr,Sb,Sg}<=20。
【分析】
上个月学的群论终于派上用场了23333……
这题几乎就是一道等价类计数的练习题？注意到输入数据中黑体部分已经明确指出了输入数据中的所有置换恰好是一个完整的置换群（单位元是确定的，因此这里无需输入），那么根据Burnside引理，我们就有：等价类个数等于置换群中每个元素的“不动点”个数的平均值。其中“不动点”是指在置换$p$的作用下保持不变的排列种数。
那么，这道题中的“不动点”怎么求呢？根据置换的性质，我们可以将每种“洗牌法”分解成若干个不相交循环的乘积。对于一个排列，只要保证它在每个循环中的所有元素“颜色”都相同，就可以保证它在这种“洗牌法”下是一个“不动点”。于是，我们只要将每个置换分解成k个循环，记录下各个循环的长度$len_i$，就可以将问题转化为背包问题：“有3个背包，容量分别为Sr,Sb,Sg，将k件物品放入3个背包，第i件物品重量为$len_i$，求三个背包恰好放满的方案数”。
是不是毫无编码难度？→_→ 不过还要注意一点，我们上面的分析暂时没有考虑置换群中的单位元（即置换(1,2,...n))，只要再用可重集的全排列公式求出单位元的不动点个数，加上上面dp的结果后除以m + 1就好了。（读入的m个置换外加单位元）
最后不要忘了，上面所说的所有除法都是在模p剩余系$Z_p$中进行的，要用乘逆元来实现。
2 Problem: 1004
3 User: 935671154
4 Language: C++
5 Result: Accepted
6 Time:24 ms
7 Memory:1396 kb
8 ****************************************************************/
9
10 #include <iostream>
11 #include <cctype>
12 #include <cstdio>
13 #include <vector>
14 #include <algorithm>
15 #include <cmath>
16 #include <queue>
17 using namespace std;
18 inline void getd(int &x){
19 char c = getchar();
20 bool minus = 0;
21 while(!isdigit(c) && c != ‘-‘)c = getchar();
22 if(c == ‘-‘)minus = 1, c = getchar();
23 x = c - ‘0‘;
24 while(isdigit(c = getchar()))x = x * 10 + c - ‘0‘;
25 if(minus)x = -x;
26 }
27 /*======================================================*/
28 inline void exgcd(int a, int b, int &x, int &y){
29 if(!a){x = 0, y = 1; return;}
30 exgcd(b % a, a, y, x);
31 x -= b / a * y;
32 }
33
34 const int maxn = 63, maxk = 22;
35 int R, B, G, m, mod, ans, inv, n;
36 int p[maxn], loop[maxn], len;
37 int dp[maxn][maxk][maxk] = {0};
38 int fact[maxn];
39
40 inline void init(){
41 getd(R), getd(B), getd(G), getd(m), getd(mod);
42 n = R + B + G;
43 int i;fact[0] = 1;
44 for(i = 1;i <= n;++i) fact[i] = fact[i-1] * i % mod;
45 int x, y, t; ans = fact[n];
46 t = fact[R] * fact[B] * fact[G] % mod;
47 exgcd(t, mod, x, y);
48 ans = ans * x % mod;
49 if(ans < 0) ans += mod;
50 exgcd(m + 1, mod, x, y);
51 inv = x < 0 ? x + mod : x;
52 }
53
54 inline void analy(){
55 len = 0;
56 bool used[maxn] = {0};
57 int i, j, cnt;
58 for(i = 1;i <= n;++i){
59 if(!used[i]){
60 used[i] = 1, cnt = 1, j = p[i];
61 while(j != i){
62 used[j] = 1; ++cnt;
63 j = p[j];
64 }
65 loop[++len] = cnt;
66 }
67 }
68 }
69
70 inline int count(){
71 int i, j, k, s = 0;
72 dp[0][0][0] = 1;
73 for(i = 1;i <= len;++i){
74 s += loop[i];
75 for(j = 0;j <= R;++j) for(k = 0;k <= B;++k){
76 dp[i][j][k] = 0;
77 if(j >= loop[i])dp[i][j][k] += dp[i-1][j-loop[i]][k];
78 if(k >= loop[i])dp[i][j][k] += dp[i-1][j][k-loop[i]];
79 if(s-i-j >= loop[i])dp[i][j][k] += dp[i-1][j][k];
80 dp[i][j][k] %= mod;
81 }
82 }
83 return dp[len][R][B] % mod;
84 }
85
86 inline void work(){
87 int i;
88 while(m--){
89 for(i = 1;i <= n;++i) getd(p[i]);
90 analy();
91 ans = (ans + count()) % mod;
92 }
93 printf("%d\n", ans * inv % mod);
94 }
95
96 int main(){
97 #if defined DEBUG
98 freopen("test", "r", stdin);
99 #endif
100
101 init();
102
103 work();
104
105 #if defined DEBUG
106 cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
107 #endif
108 return 0;
109 }
[BZOJ1004](HNOI 2008) Cards