[题解] [HNOI2008] Cards

给你 $n$ 张牌要求染成红、蓝、绿三种颜色（求染出 $S_r$ 张红色，$S_b$ 张蓝色，$S_g$ 张绿色），并给定了 $m$ 种洗牌方案，这些洗牌方案满足：

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

问有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法（即可以使用多种洗牌法，而每种方法可以使用多次）洗成另一种。

$m\le 60$，$\max{S_r,S_b,S_g}\le20$

题目链接

---

思路

弱智 Burnside 引理板子题

很容易看出题目中的洗牌方案是满足置换群的定义的，因此我们可以直接上 Burnside 引理。

我们来看一下 Burnside 引理的公式：
$$
\text{轨道数}=\frac{1}{\left|G\right|}\sum_{g\in G}\left|X^g\right|
$$
其中 $G$ 代表置换群， $X^g$ 代表 $X$ 中在 $g$ 这一置换作用下的不动元素，$\left|object\right|$ 代表取 $object$ 的大小。

那么题目中的问题就被转化为了如何求得在一种洗牌方案下不变的染色方案个数。

如果读者对 Polya 定理有一定认识，那么应该能想到找出洗牌方案中的循环节。循环节中的元素颜色必须相同，其他则无要求。

随后，我们需要求出对于每一种洗牌方案，用这三种指定个数的颜色染色的不变染色方案个数——这个问题可以用 dp 解决。

我们令 $f[i][j][k]$ 为三种颜色还需要各染 $i,j,k$ 个时的方案数。显然 $f[0][0][0]=1$，同时有转移方程：
$$
f[i][j][k]=f[i-len][j][k]+f[i][j-len][k]+f[i][j][k-len]
$$
这个 dp 对于每一个循环节都要跑一遍，其中 $len$ 为当前循环节的长度。最后我们要求的答案就是 $f[S_r][S_g][S_b]$。

代码

mivik.h

// Mivik 2020.4.27
#include <mivik.h>

MI cin;

const int $s = 85;
const int $n = 65;

int mod;

inline void Add(int &x, int y) {
	if ((x += y) >= mod) x -= mod;
}

int n, m;
int sr, sg, sb;
int f[$s][$s][$s];
int ind[$n], av[$n];
inline int ksm(int x, int p = mod - 2) {
	int ret = 1;
	for (; p; p >>= 1, (x *= x) %= mod)
		if (p & 1) (ret *= x) %= mod;
	return ret;
}
inline int purge(int x) {
	int cnt = 0;
	while (true) {
		const int tar = ind[x];
		if (!tar) break;
		ind[x] = 0;
		x = tar;
		++cnt;
	}
	return cnt;
}
inline int stable() {
	int tot = 0;
	for (int i = 1; i <= n; ++i)
		if (ind[i]) av[++tot] = purge(i);
	f[0][0][0] = 1;
	for (int q = 1; q <= tot; ++q) {
		const int cur = av[q];
		for (int i = sr; ~i; --i)
			for (int j = sg; ~j; --j)
				for (int k = sb; ~k; --k) f[i][j][k] = (((i >= cur) ? f[i - cur][j][k] : 0) + ((j >= cur) ? f[i][j - cur][k] : 0) + ((k >= cur) ? f[i][j][k - cur] : 0)) % mod;
	}
	return f[sr][sg][sb];
}
int main() {
	cin > sr > sg > sb > m > mod;
	n = sr + sg + sb;

	for (int i = 1; i <= n; ++i) ind[i] = i;
	int ans = stable();
	const int invm = ksm(m + 1);
	while (m--) {
		for (int i = 1; i <= n; ++i) cin > ind[i];
		Add(ans, stable());
	}
	ans = ans * invm % mod;
	cout < ans < endl;
}

坑点

• 转移那里需要判断一下 $i,j,k$ 是否大于等于 $len$
• 转移时要取模~~（也就只有我想不到了）~~

（函数名奇妙请无视）