bzoj 1004

[HNOI2008]Cards

Description

小春现在很清闲, 面对书桌上的 $N$ 张牌, 他决定给每张染色, 目前小春只有 $3$ 种颜色: 红色, 蓝色, 绿色. 他询问 Sun 有多少种染色方案, Sun 很快就给出了答案.

进一步, 小春要求染出 $Sr$ 张红色, $Sb$ 张蓝色, $Sg$ 张绿色. 他又询问有多少种方案, Sun 想了一下, 又给出了正确答案.

最后小春发明了 $m$ 种不同的洗牌法, 这里他又问 Sun 有多少种不同的染色方案. 两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种. Sun 发现这个问题有点难度, 决定交给你, 答案可能很大, 只要求出答案除以 $p$ 的余数( $p$ 为质数).

Input

第一行输入 $5$ 个整数： $Sr, Sb, Sg, m, p(m \le 60, m+1<p<100)$ . $n=Sr+Sb+Sg$ .

接下来 $m$ 行，每行描述一种洗牌法，每行有 $n$ 个用空格隔开的整数 $X_1X_2...X_n$ ，恰为 $1$ 到 $n$ 的一个排列，表示使用这种洗牌法，第 $i$ 位变为原来的 $X_i$ 位的牌. 输入数据保证任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

Output

不同染法除以 $p$ 的余数

Sample Input

1 1 1 2 7
2 3 1
3 1 2

Sample Output

题解

"输入数据保证任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替." 就是在说给出的置换满足封闭性.

"且对每种洗牌法，都存在一种洗牌法使得能回到原状态。" 表示每个置换都存在一个逆元.

这样，再补充上置换 $(1)(2)\cdots(n)$ ，这些置换构成一个大小为 $m+1$ 的置换群. 由 Burnside 引理，不等价的着色数为：

$\frac{1}{|G|}\sum_{g \in G}{|S(g)|}$

其中 $S(g)$ 为所有着色方案中对置换 $g$ 保持不变的着色集合. 在本题中，也就是将置换 $g$ 的每个循环节染成同一种颜色的方案数.

对于每个置换，求出循环节数量 $R$ 和每个循环节的长度 $l_i$ 后，使用动态规划求出方案数. 设 $f[x][i][j][k]$ 表示考虑到第 $x(1 \le x \le R)$ 个循环节时用掉 $i$ 个红色、 $j$ 个蓝色、 $k$ 个绿色的方案数. 则

$\begin{aligned} f[x][i][j][k] =&\: [i \ge l_x]\cdot{}f[x-1][i - l_x][j][k] \\ +&\: [j \ge l_x]\cdot{}f[x-1][i][j - l_x][k] \\ +&\: [k \ge l_x]\cdot{}f[x-1][i][j][k - l_x] \end{aligned}$

其中 $[\text{bool expression}]$ 表示当且仅当其中的表达式为真时值为 $1$ ，否则为 $0$ .

最后除以 $|G|$ 要用乘上 $|G|$ 的逆元代替，可以用费马小定理或扩展欧几里得求出 $m+1$ 的逆元.

代码

#include <cstdio>
#include <bitset>
#include <cstring>

using namespace std;
typedef long long int ll;

ll p;
void add(ll &dest, ll delta) { dest = (dest + delta) % p; }
void mul(ll &dest, ll times) { dest = (dest * times) % p; }
ll qow(ll a, ll x)
{
    ll ret = 1ll;
    while (x)
    {
        if (1 & x) mul(ret, a);
        mul(a, a);
        x >>= 1;
    }
    return ret;
}

#define MAXC (1 << 5)
#define MAXN (1 << 7)

int n;
int sr, sb, sg;
int m;
int to[MAXN];

bitset<MAXN> vis;
int ncir;
int sz[MAXN];
ll f[MAXC][MAXC][MAXC];
ll count(void)
{
    ncir = 0;
    memset(sz, 0, sizeof sz); memset(f, 0, sizeof f);
    vis.reset();
    for (int i = 1; i <= n; i++)
    {
        if (vis.test(i)) continue;
        int v = i;
        while (!vis.test(v))
        {
            sz[ncir]++;
            vis.set(v);
            v = to[v];
        }
        ncir++;
    }
    f[0][0][0] = 1ll;
    for (int c = 0; c < ncir; c++)
    {
        for (int i = sr; i >= 0; i--)
            for (int j = sb; j >= 0; j--)
                for (int k = sg; k >= 0; k--)
                {
                    if (i >= sz[c]) add(f[i][j][k], f[i - sz[c]][j][k]);
                    if (j >= sz[c]) add(f[i][j][k], f[i][j - sz[c]][k]);
                    if (k >= sz[c]) add(f[i][j][k], f[i][j][k - sz[c]]);
                }
    }
    return f[sr][sb][sg];
}

int main(void)
{
    int i, j;
    ll ans = 0ll;
    scanf("%d%d%d%d%lld", &sr, &sb, &sg, &m, &p);
    n = sr + sb + sg;
    for (i = 0; i < m; i++)
    {
        for (j = 1; j <= n; j++)
            scanf("%d", to + j);
        add(ans, count());
    }
    for (i = 1; i <= n; i++) to[i] = i; add(ans, count());
    mul(ans, qow(m + 1, p - 2));
    printf("%lld\n", ans);
    return 0;
}

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
77
78
79
80
81
82
83

# bzoj 1004

# [HNOI2008]Cards

# Description

# Input

# Output

# Sample Input

# Sample Output

# 题解

# 代码