题目概述

有 $R$ 张红牌，$B$ 张蓝牌，$G$ 张绿牌。现在给出 $m$ 种洗牌法（把 $i$ 位的放到 $x_i$ 上），如果两套牌可以通过 $m$ 种洗牌法洗成同一套则这两套牌相同。问有多少套不同的牌。

解题报告

终于填了点置换神坑……先来讲点（完全）不严谨的定义：

1. 置换：把原先 $i$ 位置的换到 $x_i$ （ $x$ 是个排列），两个置换可以乘起来。一个置换可以由若干个循环组成。
2. 置换群：由很多置换组成，需要满足一些条件：封闭性（两个置换乘起来之后依然是群中的置换），有单位元（ $x_i=i$ ），有逆元，可以结合。
3. 不动点：对于一种方案，如果在某个置换中完全不改变，那么这个方案就是这个置换的一个不动点。

Burnside引理一般都用来处理染色问题，如果两种染色经过置换之后可以变成同样的染色那么这两个染色等价，如何计算不等价的染色方案呢？上公式：

$$ {1\over|G|}\sum_{i=1}^{|G|}C(a_i) $$

其中 $G$ 是置换群，$a_i$ 表示第 $i$ 个置换，$C(a_i)$ 表示在 $a_i$ 下的不动点个数。

那么这道题就是给出了 $m$ 个置换，每个置换的不动点是这样的：该置换的循环中的颜色全一样。

先 $O(n)$ 把置换拆成循环，然后不动点个数可以用背包处理出来。

题目里保证了封闭性和逆元，但是没有单位元，单位元就是不洗牌，加上去套Burnside就好了。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=60,maxm=60,maxa=20;

int R,B,G,n,m,MOD,x[maxn+5],f[maxa+5][maxa+5][maxa+5],ans,tot,si[maxn+5],ti,vis[maxn+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=w*w%MOD) if (b&1) s=s*w%MOD;return s;}
inline int Count(){
    memset(f,0,sizeof(f));f[0][0][0]=1;ti++;tot=0;
    for (int i=1;i<=n;i++)
        if (vis[i]<ti) {si[++tot]=0;for (int j=i;vis[j]<ti;j=x[j]) si[tot]++,vis[j]=ti;}
    for (int i=1;i<=tot;i++)
        for (int r=R;~r;r--)
            for (int b=B;~b;b--)
                for (int g=G;~g;g--){
                    if (r>=si[i]) AMOD(f[r][b][g],f[r-si[i]][b][g]);
                    if (b>=si[i]) AMOD(f[r][b][g],f[r][b-si[i]][g]);
                    if (g>=si[i]) AMOD(f[r][b][g],f[r][b][g-si[i]]);
                }return f[R][B][G];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d%d%d",&R,&B,&G,&m,&MOD);n=R+B+G;for (int i=1;i<=n;i++) x[i]=i;ans+=Count();
    for (int i=1;i<=m;i++) {for (int i=1;i<=n;i++) scanf("%d",&x[i]);ans+=Count();}
    ans=ans*Pow(m+1,MOD-2)%MOD;return printf("%d\n",ans),0;
}