1004: [HNOI2008]Cards
Time Limit: 10 Sec Memory Limit: 162 MB[][][]Description
小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).
Input
第一行输入 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种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。
Output
不同染法除以P的余数
Sample Input
1 1 1 2 7 2 3 1 3 1 2
Sample Output
2
HINT
有2 种本质上不同的染色法RGB 和RBG，使用洗牌法231 一次可得GBR 和BGR，使用洗牌法312 一次 可得BRG和GRB。
100%数据满足 Max{Sr,Sb,Sg}<=20。
置换群
因为每种颜色的牌的数量有限制，所以不能用Polya定理
用三维背包做Burnside引理
#include#include int sr,sb,sg,sum[61],m,p,tot;int c[61],f[21][21][21];bool v[61];void mod(int &x) { x>=p ? x=x%p : x=x; }int pow(int a,int b,int p){ int r=1; while(b) { if(b&1) r=r*a,mod(r); a=a*a,mod(a),b>>=1; } return r;}int work(){ memset(v,0,sizeof(v)); int now,cnt=0; memset(sum,0,sizeof(sum)); for(int i=1;i<=tot;i++) { if(v[i]) continue; now=i; cnt++; while(!v[now]) { v[now]=true; sum[cnt]++; now=c[now]; } } memset(f,0,sizeof(f)); f[0][0][0]=1; for(int i=1;i<=cnt;i++) for(int r=sr;r>=0;r--) for(int b=sb;b>=0;b--) for(int g=sg;g>=0;g--) { if(r>=sum[i]) f[r][b][g]+=f[r-sum[i]][b][g]; if(b>=sum[i]) f[r][b][g]+=f[r][b-sum[i]][g]; if(g>=sum[i]) f[r][b][g]+=f[r][b][g-sum[i]]; mod(f[r][b][g]); } return f[sr][sb][sg];}int main(){ scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p); tot=sr+sb+sg; for(int i=1;i<=tot;i++) c[i]=i; int ans=work(); for(int i=1;i<=m;i++) { for(int j=1;j<=tot;j++) scanf("%d",&c[j]); ans+=work(); mod(ans); } int inv=pow(m+1,p-2,p); ans*=inv; mod(ans); printf("%d",ans);}