小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).

第一行输入 5 个整数：Sr,Sb,Sg,m,p(m<=60,m+1<p<100)。n=Sr+Sb+Sg。
接下来 m 行，每行描述一种洗牌法，每行有 n 个用空格隔开的整数 X1X2...Xn，恰为 1 到 n 的一个排列，表示使用这种洗牌法，第 i位变为原来的 Xi位的牌。输入数据保证任意多次洗牌都可用这 m种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。

不同染法除以P的余数

  1 //It is made by wfj_2048~  2 #include <algorithm>  3 #include <iostream>  4 #include <complex>  5 #include <cstring>  6 #include <cstdlib>  7 #include <cstdio>  8 #include <vector>  9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define inf (1<<30) 15 #define il inline 16 #define RG register 17 #define ll long long 18 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 19  20 using namespace std; 21  22 int f[65][25][25][25],fa[65],sz[65],s[65],x[65],n,m,M,p,sr,sb,sg,cnt,ans; 23  24 il int gi(){ 25     RG int x=0,q=1; RG char ch=getchar(); 26     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 27     if (ch==‘-‘) q=-1,ch=getchar(); 28     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 29     return q*x; 30 } 31  32 il ll qpow(RG ll a,RG ll b){ 33     RG ll ans=1; 34     while (b){ 35     if (b&1) ans=ans*a%p; 36     a=a*a%p,b>>=1; 37     } 38     return ans; 39 } 40  41 il int find(RG int x){ 42     return fa[x]==x ? x : fa[x]=find(fa[x]); 43 } 44  45 il void work(){ 46     sr=gi(),sb=gi(),sg=gi(),m=gi(),p=gi(),n=sr+sb+sg,M=m; 47     while (M--){ 48     for (RG int i=1;i<=n;++i) fa[i]=i,sz[i]=1; cnt=0; 49     for (RG int i=1,u,v;i<=n;++i){ 50         x[i]=gi(),u=find(i),v=find(x[i]); 51         if (u!=v) fa[u]=v,sz[v]+=sz[u]; 52     } 53     memset(f,0,sizeof(f)),f[0][0][0][0]=1; 54     for (RG int i=1;i<=n;++i) if (find(i)==i) s[++cnt]=sz[i]; 55     for (RG int i=1;i<=cnt;++i) 56         for (RG int a=0;a<=sr;++a) 57         for (RG int b=0;b<=sb;++b) 58             for (RG int c=0;c<=sg;++c){ 59             if (a+s[i]<=sr){ 60                 f[i][a+s[i]][b][c]+=f[i-1][a][b][c]; 61                 if (f[i][a+s[i]][b][c]>=p) f[i][a+s[i]][b][c]-=p; 62             } 63             if (b+s[i]<=sb){ 64                 f[i][a][b+s[i]][c]+=f[i-1][a][b][c]; 65                 if (f[i][a][b+s[i]][c]>=p) f[i][a][b+s[i]][c]-=p; 66             } 67             if (c+s[i]<=sg){ 68                 f[i][a][b][c+s[i]]+=f[i-1][a][b][c]; 69                 if (f[i][a][b][c+s[i]]>=p) f[i][a][b][c+s[i]]-=p; 70             } 71             } 72     ans+=f[cnt][sr][sb][sg]; if (ans>=p) ans-=p; 73     } 74     for (RG int i=1;i<=n;++i) s[i]=1; memset(f,0,sizeof(f)),f[0][0][0][0]=1; 75     for (RG int i=1;i<=n;++i) 76     for (RG int a=0;a<=sr;++a) 77         for (RG int b=0;b<=sb;++b) 78         for (RG int c=0;c<=sg;++c){ 79             if (a+s[i]<=sr){ 80             f[i][a+s[i]][b][c]+=f[i-1][a][b][c]; 81             if (f[i][a+s[i]][b][c]>=p) f[i][a+s[i]][b][c]-=p; 82             } 83             if (b+s[i]<=sb){ 84             f[i][a][b+s[i]][c]+=f[i-1][a][b][c]; 85             if (f[i][a][b+s[i]][c]>=p) f[i][a][b+s[i]][c]-=p; 86             } 87             if (c+s[i]<=sg){ 88             f[i][a][b][c+s[i]]+=f[i-1][a][b][c]; 89             if (f[i][a][b][c+s[i]]>=p) f[i][a][b][c+s[i]]-=p; 90             } 91         } 92     ans+=f[n][sr][sb][sg]; if (ans>=p) ans-=p; 93     printf("%lld\n",ans*qpow(m+1,p-2)%p); return; 94 } 95  96 int main(){ 97     File("cards"); 98     work(); 99     return 0;100 }