Description
Solution
组合数学向来不好（其实啥也不好）的我，面对这个题，直接一脸懵B，在洗牌那里卡了好久，看了题解才知道，洗牌原来就是置换！这是Burnside引理的直接应用，亏我还学过Burnside，真是练习量太少，知识无法灵活运用，唉~，滚去刷题吧。
这道题用Burnside引理时有一个要注意的是数方案数的时候不要超过颜色限制，加一个递推即可。别忘了不变也是一个置换。
#include#include const int N = 100;int mod, n, m;int ch[N][N], sr, sb, sg;int f[N][N][N];int b[N], vis[N];int pow_mod(int x, int b, int mod) { int ans = 1; for (; b; b >>= 1) { if (b & 1) ans = ans * x % mod; x = x * x % mod; } return ans % mod;}int main () { scanf("%d%d%d%d%d", &sr, &sb, &sg, &m, &mod); n = sr + sb + sg; int ans = 0; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &ch[i][j]); } int now = 1, cnt = 0; memset(vis, 0, sizeof vis); memset(b, 0, sizeof b); memset(f, 0, sizeof f); for (int j = 1; j <= n; ++j) if (!vis[j]) { now = j; vis[j] = 1; b[++cnt] = 1; while (!vis[ch[i][now]]) { vis[ch[i][now]] = 1; now = ch[i][now]; b[cnt]++; } } f[0][0][0] = 1; for (int k = 1, s = 0; k <= cnt; ++k) { s += b[k]; for (int j = 0; j <= sr; ++j) { for (int l = 0; l <= sg; ++l) { int p = s - j - l; if (p > sb || p < 0) continue; if (j >= b[k]) f[k][j][l] += f[k-1][j-b[k]][l]; if (l >= b[k]) f[k][j][l] += f[k-1][j][l-b[k]]; if (p >= b[k]) f[k][j][l] += f[k-1][j][l]; f[k][j][l] %= mod; } } } ans = (ans + f[cnt][sr][sg]) % mod; } memset(f, 0, sizeof f); f[0][0][0] = 1; for (int k = 1; k <= n; ++k) { for (int j = 0; j <= sr; ++j) { for (int l = 0; l <= sg; ++l) { int p = k - j - l; if (p > sb || p < 0) continue; if (j >= 1) f[k][j][l] += f[k-1][j-1][l]; if (l >= 1) f[k][j][l] += f[k-1][j][l-1]; if (p >= 1) f[k][j][l] += f[k-1][j][l]; f[k][j][l] %= mod; // mark } } } ans = (ans + f[n][sr][sg]) % mod * pow_mod(m+1, mod-2, mod) % mod; printf("%d\n", ans); return 0;}
Note
mark那里我一开始竟然忘写了。。。