【BZOJ1004】Cards

  中间有一题不放进博客实在不爽，就照搬原来博客里写过的东西了...

      首先这是个置换群。由于之前没学过置换群于是去补了一下。主要是Burnside引理与Polya定理，由于太弱看了很久。

      然后就可以开始应用了，但是由于有颜色数量限制不能直接使用Polya定理，需要用Burnside引理并且有比较深刻的理解。大概就是如果一个方案在置换p下不变，那么这个置换的同一个循环节上的颜色是一样的。由此计算不变的方案数。

#include <cstdio>
#include <cstring>
using namespace std;
const int maxs=22,maxn=65;
 
int D[maxn][maxn];
int f[maxs][maxs][maxs];
int t[maxn],vis[maxn],cnt;
int sr,sb,sg,n,m,p,ans;
 
void Circle(int o)
{
    memset(vis,0,sizeof(vis));
    memset(t,0,sizeof(t));
    cnt=0;
    for (int i=1;i<=n;i++) if (!vis[i])
    {
        t[++cnt]=1;
        vis[i]=1;
        int x=D[o][i];
        while (x!=i) vis[x]=1,t[cnt]++,x=D[o][x];
    }
}
 
int DP()
{
    memset(f,0,sizeof(f));
    f[0][0][0]=1;
    for (int o=1;o<=cnt;o++)
    for (int i=sr;i>=0;i--)
    for (int j=sb;j>=0;j--)
    for (int k=sg;k>=0;k--)
    {
        if (i>=t[o]) f[i][j][k]+=f[i-t[o]][j][k];
        if (j>=t[o]) f[i][j][k]+=f[i][j-t[o]][k];
        if (k>=t[o]) f[i][j][k]+=f[i][j][k-t[o]];
        f[i][j][k]%=p;
    }
    return f[sr][sb][sg];
}
 
void Extended_GCD(int a,int b,int &x,int &y)
{
    if (b==0) {x=1;y=0;return;}
    Extended_GCD(b,a%b,x,y);
    int temp=y;y=x-(a/b)*y;x=temp;
}
 
void Ans_Dividem()
{
    int x,y;
    Extended_GCD(m,p,x,y);
    x=(x%p+p)%p;
    ans=(ans*x)%p;
}
 
int main()
{
    scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&p);
    n=sr+sb+sg;
    for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) scanf("%d",&D[i][j]);
    m++;
    for (int i=1;i<=n;i++) D[m][i]=i;
    for (int i=1;i<=m;i++) Circle(i),ans=(ans+DP())%p;
    Ans_Dividem();
    printf("%d\n",ans);
    return 0;
}