n n 张卡牌染成 a a 张红色,b b 张蓝色,c c 张绿色。同时给定 m m 种洗牌方法,求有多少种不同染色的方案数。两种染色方法相同当且仅当一种染色方法可以同过任意洗牌方式变成另一种。

题解

使用 Burnside 引理。

染色集中的非等价染色数等于在置换群的每个置换作用下保持不变的着色之和的平均数。。懒得证了,组合数学上讲的还是很好的嘛。蛤蛤蛤团长就是这样的无耻。

至于统计在每个置换群作用下保持不变的着色数,可以用一个 DP 解决。

首先找出置换的循环节,这里这里只需要保证置换的循环节全部都是一种颜色就可以保证在这种置换的作用下染色保持不变了。不证明,YY一下发现它就是对的。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#include <algorithm>
const int MAX_X = 20;
const int MAX_N = 60;
const int MAX_M = 60;
int a, b, c, n, m, mod;
inline int calc(int *map) {
bool flag[MAX_M + 1] = { false };
std::vector<int> v;
for (int i = 1; i <= n; i++) {
int x = 0;
for (int j = i; !flag[j]; j = map[j]) {
flag[j] = true;
x++;
}
if (x) v.push_back(x);
}
static int f[MAX_X + 1][MAX_X + 1][MAX_X + 1];
memset(f, 0, sizeof(f));
f[0][0][0] = 1;
for (std::vector<int>::const_iterator it = v.begin(); it != v.end(); it++) {
for (int i = a; i >= 0; i--) {
for (int j = b; j >= 0; j--) {
for (int k = c; k >= 0; k--) {
if (i >= *it) (f[i][j][k] += f[i - *it][j][k]) %= mod;
if (j >= *it) (f[i][j][k] += f[i][j - *it][k]) %= mod;
if (k >= *it) (f[i][j][k] += f[i][j][k - *it]) %= mod;
}
}
}
}
return f[a][b][c];
}
inline void exgcd(int a, int b, int &g, int &x, int &y) {
if (!b) g = a, x = 1, y = 0;
else exgcd(b, a % b, g, y, x), y -= x * (a / b);
}
inline int inv(int x) {
int g, r, y;
exgcd(x, mod, g, r, y);
return (r % mod + mod) % mod;
}
int main() {
scanf("%d %d %d %d %d", &a, &b, &c, &m, &mod);
n = a + b + c;
static int map[MAX_N + 1];
int sum = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) scanf("%d", &map[j]);
(sum += calc(map)) %= mod;;
}
for (int i = 1; i <= n; i++) map[i] = i;
(sum += calc(map)) %= mod;
int ans = sum * inv(m + 1) % mod;
printf("%d\n", ans);
return 0;
}