BZOJ1004【HNOI2008】Cards < Burnside引理+背包DP >

Problem

【HNOI2008】Cards

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162MB}$

Description

小春现在很清闲，面对书桌上的$N$张牌，他决定给每张染色。
目前小春只有$3$种颜色：红色，蓝色，绿色。他询问$\mathrm{Sun}$有多少种染色方案，$\mathrm{Sun}$很快就给出了答案。
进一步，小春要求染出$Sr$张红色，$Sb$张蓝色，$Sg$张绿色。他又询问有多少种方案，$\mathrm{Sun}$想了一下，又给出了正确答案。
最后小春发明了$M$种不同的洗牌法，他又问$\mathrm{Sun}$有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。
$\mathrm{Sun}$发现这个问题有点难度，决定交给你。
答案可能很大，只要求出答案除以$P$的余数（$P$为质数）。

Input

第一行输入$5$个整数：$Sr,Sb,Sg,m,p$。$n=Sr+Sb+Sg$。
接下来$m$行，每行描述一种洗牌法，每行有$n$个用空格隔开的整数$X_1X_2\cdots 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

2

Explanation

有$2$种本质上不同的染色法RGB和RBG，使用洗牌法231一次可得GBR和BGR，使用洗牌法312一次 可得BRG和GRB。

HINT

$100\%$数据满足$\max\lbrace Sr,Sb,Sg\rbrace\le20,\;m\le60,\;m+1<p<100$。

标签：Burnside引理 背包DP

Solution

挺好的一道群论基础题，一看是$\mathrm{Polya}$定理裸题，再看发现要转化为背包$\mathrm{DP}$数不动点。

将每一种洗牌方式看成一种置换，这些置换所形成的群称为$G$。将所有排列的集合称为$X$。那么对于群在集合上的作用$G\times X\to X$，我们想计算其无交轨道数，即$|X/G|$。
对于一个置换$g\in G$，令$X^g=\lbrace x\in X|gx=x\rbrace$，即关于$g$的轨道上的不动点数目。
由$\mathrm{Burnside}$引理可知，有

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$$

由于题目中对每种颜色的数量都有限制，我们无法直接套用$\mathrm{Polya}$定理，因此只能按照$\mathrm{Burnside}$引理将每种置换对应的轨道上不动点数的和算出来，再计算$|X/G|$。

考虑对于一种置换（洗牌方式），如何计算其不动点数。
首先，对于一个置换，我们一定可以将其表示为若干轮换作用起来的形式。
例如，对于置换

$$\begin{pmatrix} 1&2&3&4&5\\ 2&5&4&3&1\\ \end{pmatrix}$$

我们可以将其分为不相关的两部分

$$\begin{pmatrix} 1&2&5\\ 2&5&1\\ \end{pmatrix} \begin{pmatrix} 3&4\\ 4&3\\ \end{pmatrix}$$

再写成两个轮换相作用的形式

$$\begin{pmatrix} 1&2&5 \end{pmatrix} \begin{pmatrix} 3&4 \end{pmatrix}$$

由于每个轮换内部都可以任意交换，对于一种置换，其不动点的每个轮换内部一定是涂的相同颜色。这意味着我们可以将一个轮换作为一个整体看待。
于是我们预处理出这个置换每个轮换的大小，将一个轮换看作大小为其长度的物品，做背包$\mathrm{DP}$。
设第$i$个物品大小为$sz_i$。用$f[i][a][b]$表示前$i$个物品，有$a$个是第$1$种颜色，有$b$个是第$2$种颜色，此状态下的染色方案数。那么染第$3$种颜色的物品数为$\sum_{j=1}^{i}sz_j-a-b$。有三种转移：

1. 若$a\ge sz_i$，则$f[i][a][b]=f[i][a][b]+f[i-1][a-sz_i][b]$
2. 若$b\ge sz_i$，则$f[i][a][b]=f[i][a][b]+f[i-1][a][b-sz_i]$
3. 若$c\ge sz_i$，则$f[i][a][b]=f[i][a][b]+f[i-1][a][b]$

对于每个输入的洗牌方式，先$\mathrm{DFS}$求出$sz$数组，再$\mathrm{DP}$求出不动点个数并累加即可得到总不动点个数。注意这里还需要加上恒等置换（即所有位置都不动）的不动点数，即$\frac{n!}{A!\cdot B!\cdot C!}$。
答案等于$\frac{不动点总数}{m+1}$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, A, B, C, num;
int p[65], cnt[65], tot[65];
lnt f[65][65][65], pw[65], P;
bool mrk[65];
lnt inv(lnt x) {
    lnt ret = 1;
    for (lnt k = P-2; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
void DFS(int u, int sz) {
    if (mrk[u]) {cnt[++num] = sz; return;}
    mrk[u] = true, DFS(p[u], sz+1);
}
int main() {
    read(A), read(B), read(C), n = A+B+C, read(m), read(P);
    pw[0] = 1; for (int i = 1; i <= n; i++) pw[i] = pw[i-1]*i%P;
    lnt sum = pw[n]*inv(pw[A])%P*inv(pw[B])%P*inv(pw[C])%P;
    for (int T = 1; T <= m; T++) {
        num = 0; memset(mrk, false, sizeof mrk);
        for (int i = 1; i <= n; i++) read(p[i]);
        for (int i = 1; i <= n; i++) if (!mrk[i]) DFS(i, 0);
        for (int i = 1; i <= num; i++) tot[i] = tot[i-1]+cnt[i];
        for (int i = 1; i <= num; i++)
            for (int a = 0; a <= A; a++)
                for (int b = 0; b <= B; b++) {
                    int c = tot[i]-a-b; f[i][a][b] = 0;
                    if (a >= cnt[i]) (f[i][a][b] += f[i-1][a-cnt[i]][b]) %= P;
                    if (b >= cnt[i]) (f[i][a][b] += f[i-1][a][b-cnt[i]]) %= P;
                    if (c >= cnt[i]) (f[i][a][b] += f[i-1][a][b]) %= P;
                }
        (sum += f[num][A][B]) %= P;
    }
    return printf("%lld\n", sum*inv(m+1)%P), 0;
}