题解 P1446 【[HNOI2008]Cards】

· · 题解

因为任意置换的组合一定还在这个置换集合里，注意加上单位置换，此时给出的置换是一个置换群。可以直接上 Burnside 引理。

那么只需要考虑每个置换下的不动点。根据给出的置换很容易求出循环的个数。

考虑每一个循环，他们内部的位置的染色必须是相同的，所以单独考虑每个循环染那种颜色，可以通过一个类似背包的过程实现。

  f[0][0][0] = 1;
  for (rg int i = 1; i <= tot; ++i)
    for (rg int nr = r; ~nr; --nr)
      for (rg int nb = b; ~nb; --nb)
        for (rg int ng = g; ~ng; --ng) {
          if (nr >= sz[i]) f[nr][nb][ng] = (f[nr][nb][ng] + f[nr-sz[i]][nb][ng]) % mod;
          if (nb >= sz[i]) f[nr][nb][ng] = (f[nr][nb][ng] + f[nr][nb-sz[i]][ng]) % mod;
          if (ng >= sz[i]) f[nr][nb][ng] = (f[nr][nb][ng] + f[nr][nb][ng-sz[i]]) % mod;
        }
  return f[r][b][g];

即 f[i][j][k] 表示三种颜色分别用了多少的方案数。

然后把每个置换的不动点数求和再乘上总置换数 (m+1) 的逆元即可。

Hack：注意 \frac{(a+b+c)!}{a!b!c!(m+1)} 的公式是错的！

这个公式只考虑了单位置换下的不动点数，很容易被卡掉。

2 1 0 1 7
3 2 1

这组数据就可以卡掉了。

此数据单位置换下不动点有 RBR,RRB,BRR

给出置换下不动点有 RBR

根据 Burnside 引理答案为 \frac{3+1}{2}=2 ，而所谓公式得出结果为 \frac{3}{2} ，甚至不是整数。

最后附上代码。

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 60
#define gc getchar
#define rg register
using namespace std;

inline int rd() {
  rg int x = 0;
  rg bool f = 0;
  rg char c = gc();
  while (!isdigit(c)) {
    if(c == '-') f = 1;
    c = gc();
  }
  while (isdigit(c)) {
    x = x * 10 + (c ^ 48);
    c = gc();
  }
  return f ? -x : x;
}

bool vis[N];

int r, b, g, n, m, mod;

int ans, tr[N], sz[N], f[N][N][N];

inline int calc() {
  int tot = 0;
  for (rg int nr = r; ~nr; --nr)
      for (rg int nb = b; ~nb; --nb)
        for (rg int ng = g; ~ng; --ng) f[nr][nb][ng] = 0;
  for (rg int i = 1; i <= n; ++i) vis[i] = 0;
  for (rg int i = 1, p, len; i <= n; ++i)
    if (!vis[i]) {
      p = i; len = 0;
      while (!vis[p]){
        ++len; vis[p] = 1; p = tr[p];
      }
      sz[++tot] = len;
    }
  f[0][0][0] = 1;
  for (rg int i = 1; i <= tot; ++i)
    for (rg int nr = r; ~nr; --nr)
      for (rg int nb = b; ~nb; --nb)
        for (rg int ng = g; ~ng; --ng) {
          if (nr >= sz[i]) f[nr][nb][ng] = (f[nr][nb][ng] + f[nr-sz[i]][nb][ng]) % mod;
          if (nb >= sz[i]) f[nr][nb][ng] = (f[nr][nb][ng] + f[nr][nb-sz[i]][ng]) % mod;
          if (ng >= sz[i]) f[nr][nb][ng] = (f[nr][nb][ng] + f[nr][nb][ng-sz[i]]) % mod;
        }
  return f[r][b][g];
}

inline int qpow(int x, int t) {
  int res = 1;
  while (t) {
    if (t & 1) res = (res * x) % mod;
    x = (x * x) % mod; t >>= 1;
  }
  return res;
}

int main() {
  r = rd(); b = rd(); g = rd();
  n = r + b + g; m = rd(); mod = rd();
  for (rg int i = 1; i <= m; ++i) {
    for (rg int j = 1; j <= n; ++j) tr[j] = rd();
    ans = (ans + calc()) % mod;
  }
  for (rg int j = 1; j <= n; ++j) tr[j] = j;
  ans = (ans + calc()) % mod;
  printf("%d\n", ans * qpow(m + 1, mod - 2) % mod);
  return 0;
}