Description

小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有

多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方

案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.

两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗

成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数)

Solution

Polya学习了一个

用背包来求每种置换的不动点数

（一开始忘记加不变的那种置换了…）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int n,sr,sb,sg,m,p,a[65][65],b[65],f[25][25][25],ans=0;bool vis[65];void exgcd(int a,int b,int& d,int& x,int& y){    if(!b){d=a,x=1,y=0;return;}    exgcd(b,a%b,d,y,x);y-=x*(a/b);}int inv(int a,int p){    int d,x,y;    exgcd(a,p,d,x,y);    return (x+p)%p;}int dp(int cnt){    memset(f,0,sizeof(f));    f[0][0][0]=1;    for(int i=1;i<=cnt;i++)    for(int j=sr;j>=0;j--)    for(int k=sb;k>=0;k--)    for(int l=sg;l>=0;l--)    {        f[j][k][l]=0;        if(j>=b[i])f[j][k][l]=(f[j][k][l]+f[j-b[i]][k][l])%p;        if(k>=b[i])f[j][k][l]=(f[j][k][l]+f[j][k-b[i]][l])%p;        if(l>=b[i])f[j][k][l]=(f[j][k][l]+f[j][k][l-b[i]])%p;    }    return f[sr][sb][sg];}int main(){    scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p);    n=sr+sb+sg;    for(int i=1;i<=m+1;i++)    {        if(i!=m+1)        for(int j=1;j<=n;j++)        scanf("%d",&a[i][j]);        else{              for(int j=1;j<=n;j++)            a[i][j]=j;        }        memset(vis,0,sizeof(vis));        int cnt=0;        for(int j=1;j<=n;j++)        {            if(!vis[j])            {                vis[j]=1;b[++cnt]=1;                int t=a[i][j];                while(t!=j)                {vis[t]=1;b[cnt]++;t=a[i][t];}            }        }        ans=(ans+dp(cnt))%p;    }    ans=(ans*inv(m+1,p))%p;    printf("%d\n",ans);    return 0;}