肉肉肉肉，，，

碰置换群啥的不是第一次了……这个题就是给你一堆置换（不要忘记还有一个幺元啊），然后限制颜色数量，求本质不同解个数。那么考虑使用Burnside引理，接下来考虑怎么计算每个置换的不动点数量，这个要求每个循环的颜色一致（不就事Polya定理了吗），所以说可以用背包DP搞一搞。

代码：

/**************************************************************
    Problem: 1004
    User: danihao123
    Language: C++
    Result: Accepted
    Time:156 ms
    Memory:3172 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
int sr, sb, sg, m, p;
int pow_mod(int a, int b) {
  int ans = 1, res = a;
  while(b) {
    if(1 & b) ans = (ans * res) % p;
    res = (res * res) % p; b >>= 1;
  }
  return ans;
}
int inv(int x) {
  return pow_mod(x % p, p - 2);
}
 
int d[65][21][21][21];
std::vector<int> len;
int dp() {
  int n = len.size();
  d[0][0][0][0] = 1;
  for(int i = 1; i <= n; i ++) {
    int l = len[i - 1];
    for(int j = 0; j <= sr; j ++) {
      for(int k = 0; k <= sb; k ++) {
        for(int t = 0; t <= sg; t ++) {
          d[i][j][k][t] = 0;
          if(j >= l) d[i][j][k][t] += d[i - 1][j - l][k][t];
          if(k >= l) d[i][j][k][t] += d[i - 1][j][k - l][t];
          if(t >= l) d[i][j][k][t] += d[i - 1][j][k][t - l];
          d[i][j][k][t] %= p;
        }
      }
    }
  }
  return d[n][sr][sb][sg];
}
 
int next[65]; bool vis[65];
int main() {
  scanf("%d%d%d%d%d", &sr, &sb, &sg, &m, &p);
  int n = sr + sb + sg;
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    len.push_back(1);
  }
  ans = dp();
  for(int i = 1; i <= m; i ++) {
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i ++) {
      scanf("%d", &next[i]);
    }
    len.clear();
    for(int i = 1; i <= n; i ++) {
      if(!vis[i]) {
        int p = i, cnt = 0;
        do {
          vis[p] = true; cnt ++;
          p = next[p];
        } while(p != i);
        len.push_back(cnt);
      }
    }
    ans = (ans + dp()) % p;
  }
  ans = (ans * inv(m + 1)) % p;
  printf("%d\n", ans);
  return 0;
}

• 相关文章
• 全局相关文章