首页 > 代码库 > [bzoj1004][HNOI2008][Cards] (置换群+Burnside引理+动态规划)
[bzoj1004][HNOI2008][Cards] (置换群+Burnside引理+动态规划)
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 72 3 13 1 2
Sample Output
2
HINT
有2 种本质上不同的染色法RGB 和RBG,使用洗牌法231 一次可得GBR 和BGR,使用洗牌法312 一次 可得BRG
和GRB。
100%数据满足 Max{Sr,Sb,Sg}<=20。
Solution
标准的置换群问题
有个神犇说过,置换群不是burnside就是polya
由于求解的是本质不同的染色方案,就可以判断是burnside引理的应用
burnside引理:
#include<stdio.h>#include<memory.h>inline int Rin(){ int x=0,c=getchar(),f=1; for(;c<48||c>57;c=getchar()) if(!(c^45))f=-1; for(;c>47&&c<58;c=getchar()) x=(x<<1)+(x<<3)+c-48; return x*f;}bool b[61];int s[4],n,m,md,fur[61][61],d[61],f[21][21][21],ans;int dp(int x){ memset(b,0,sizeof(b)); int top=0,v; for(int i=1;i<=n;i++) if(!b[i]){ b[i]=1; d[++top]=1; v=i; while(!b[fur[x][v]]) b[fur[x][v]]=1, d[top]++, v=fur[x][v]; } memset(f,0,sizeof(f)); f[0][0][0]=1; for(int k=1;k<=top;k++) for(int dx=s[1];dx>=0;dx--) for(int dy=s[2];dy>=0;dy--) for(int dz=s[3];dz>=0;dz--) (dx>=d[k]?(f[dx][dy][dz]=(f[dx][dy][dz]+f[dx-d[k]][dy][dz])%md):0), (dy>=d[k]?(f[dx][dy][dz]=(f[dx][dy][dz]+f[dx][dy-d[k]][dz])%md):0), (dz>=d[k]?(f[dx][dy][dz]=(f[dx][dy][dz]+f[dx][dy][dz-d[k]])%md):0); return f[s[1]][s[2]][s[3]];}void exgcd(int a,int b,int &x,int &y){ if(!b){x=1;y=0;return;} exgcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y;}int main(){ for(int i=1;i<=3;i++) s[i]=Rin(), n+=s[i]; m=Rin(),md=Rin(); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) fur[i][j]=Rin(); m++; for(int i=1;i<=n;i++) fur[m][i]=i; for(int i=1;i<=m;i++) ans=(ans+dp(i))%md; int x,y; exgcd(m,md,x,y); while(x<=0)x+=md,y-=m; printf("%d\n",ans*x%md); return 0;}
[bzoj1004][HNOI2008][Cards] (置换群+Burnside引理+动态规划)