初次接触置换群，学习了一下burnside引理和polya定理
burnside 引理：
（只是结论，证明并没有搞懂）
除了题目已给的置换，还应添加一个所有纸牌都指向它自己的置换
本质不同的染色方案为所有置换中1阶循环（也就是不变元素， 一个染色方案经过该置换后不变）的个数
这样的元素，每个置换中在同一循环节中的纸牌一定属于同一种颜色，所以可以直接进行背包dp
1 #define MAXN 70UL 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 int n, s1, s2, s3, m, p, tot, f[25][25][25], d[MAXN], a[MAXN][MAXN]; 8 bool vis[MAXN]; 9 10 int Ksm(int x, int k, int mod) { 11 int ret = 1; 12 while(k) { 13 if(k&1) ret = ret*x%mod; 14 x = x*x%mod; 15 k >>= 1; 16 } 17 return ret; 18 } 19 20 int Dp(int x) { 21 memset(vis, false, sizeof(vis[0])*(n+1)); 22 memset(d, 0, sizeof(d[0])*(tot+1)); 23 tot = 0; 24 for(int i = 1 ; i <= n ; ++ i) if(!vis[i]) { 25 ++ tot; 26 int nw = i; 27 while(!vis[nw]) ++ d[tot], vis[nw] = true, nw = a[x][nw]; 28 } 29 memset(f, 0, sizeof(f)); 30 f[0][0][0] = 1; 31 for(int l = 1 ; l <= tot ; ++ l) { 32 for(int i = s1 ; i >= 0 ; -- i) { 33 for(int j = s2 ; j >= 0 ; -- j) { 34 for(int k = s3 ; k >= 0 ; -- k) { 35 if(i>=d[l]) (f[i][j][k] += f[i-d[l]][j][k]) %= p; 36 if(j>=d[l]) (f[i][j][k] += f[i][j-d[l]][k]) %= p; 37 if(k>=d[l]) (f[i][j][k] += f[i][j][k-d[l]]) %= p; 38 } 39 } 40 } 41 } 42 return f[s1][s2][s3]; 43 } 44 45 int main() { 46 scanf("%d%d%d%d%d", &s1, &s2, &s3, &m, &p); 47 n = s1+s2+s3; 48 for(int i = 1 ; i <= m ; ++ i) { 49 for(int j = 1 ; j <= n ; ++ j) scanf("%d", &a[i][j]); 50 } 51 ++ m; 52 for(int i = 1 ; i <= n ; ++ i) a[m][i] = i; 53 int ans = 0; 54 for(int i = 1 ; i <= m ; ++ i) { 55 ans += Dp(i); 56 if(ans>p) ans -= p; 57 } 58 ans = (ans*Ksm(m, p-2, p))%p; 59 printf("%d", ans); 60 return 0; 61 }