bzoj [HNOI2008]Cards

群论第一题。

发现这题也是有颜色个数限制的，所以不能用$Polya$，只能用$Burnside$

$L={\frac{1}{|G|}}{\sum_{i=1}^{m}{D(a_{i})}}$

先$dfs$出每个循环节长度，每个循环节颜色需要一样，$dp$就好了。

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #define N 105

 using namespace std;

 int n,m,mod,na,nb,nc,nn,ans;

 int num[N],sum[N],f[N][N][N],fa[N],fac[N];

 bool vis[N];

 void dfs(int x,int now){

     vis[x]=;num[now]++;

     if(!vis[fa[x]])dfs(fa[x],now);

 }

 int qp(int a,int b){

     int c=;

     while(b){

         if(b&)c=c*a%mod;

         a=a*a%mod;b>>=;

     }

     return c;

 }

 int C(int a,int b){

     if(b<||b>a)return ;

     if(!b||a==b)return ;

     return fac[a]*qp(fac[b],mod-)%mod*qp(fac[a-b],mod-)%mod;

 }

 int main(){

     scanf("%d%d%d%d%d",&na,&nb,&nc,&m,&mod);

     n=na+nb+nc;

     fac[]=;

     for(int i=;i<=;i++)fac[i]=fac[i-]*i%mod;

     for(int t=;t<=m;t++){

         for(int i=;i<=n;i++)

             scanf("%d",&fa[i]);

         memset(vis,,sizeof vis);

         memset(num,,sizeof num);

         memset(f,,sizeof f);

         nn=;

         for(int i=;i<=n;i++)

             if(!vis[i]){

                 dfs(i,++nn);

                 sum[nn]=sum[nn-]+num[nn];

             }

         f[][][]=;

         for(int i=;i<=nn;i++){

             for(int j=;j<=na;j++){

                 if(j>sum[i-])break;

                 for(int k=;k<=nb;k++){

                     if(j+k>sum[i-])break;

                     int l=sum[i-]-j-k;

                     if(l>nc)break;

                     if(j+num[i]<=na)f[i][j+num[i]][k]+=f[i-][j][k];

                     if(k+num[i]<=nb)f[i][j][k+num[i]]+=f[i-][j][k];

                     if(l+num[i]<=nc)f[i][j][k]+=f[i-][j][k];

                 }

             }

         }

         ans+=f[nn][na][nb];

     }

     (ans+=C(n,na)*C(n-na,nb))%=mod;

     (ans*=qp(m+,mod-))%=mod;

     printf("%d\n",ans);

     return ;

 }