BZOJ1004 HNOI2008Cards（Burnside引理+动态规划）

　　直接给了一个置换群（当然要自己手动加上不洗牌的情况）。考虑求不动点数量即可。对于一个置换，求出所有循环的长度，然后设f[i][x][y]为给前i个循环着色后，用了x张红色卡片、y张绿色卡片的方案数，dp一发即可。

　　upd：为啥我写的应该不是假算法却好像也被hack掉了？不管了已经忘了这是啥题肯定哪写挂了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 66

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,A,B,C,m,P,a[N],cycle[N],f[N][N][N],ans;

bool flag[N];

int calc()

{

    memset(f,,sizeof(f));f[][][]=;int s=;

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

    {

        s+=cycle[j];

        for (int x=;x<=A;x++)

            for (int y=;y<=B;y++)

            {

                int z=s-x-y;if (z>C) continue;

                if (x>=cycle[j]) f[j][x][y]+=f[j-][x-cycle[j]][y];

                if (y>=cycle[j]) f[j][x][y]+=f[j-][x][y-cycle[j]];

                if (z>=cycle[j]) f[j][x][y]+=f[j-][x][y];

                f[j][x][y]%=P;

            }

    }

    return f[n][A][B];

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj1004.in","r",stdin);

    freopen("bzoj1004.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    A=read(),B=read(),C=read(),m=read(),P=read();

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

    {

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

        a[read()]=j;

        memset(flag,,sizeof(flag));n=;

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

        if (!flag[j])

        {

            int x=a[j];flag[j]=;cycle[++n]=;

            while (x!=j) flag[x]=,cycle[n]++,x=a[x];

        }

        ans+=calc();

    }

    n=A+B+C,m++;for (int i=;i<=n;i++) cycle[i]=;ans+=calc();

    for (int i=;i<P;i++) if (i*m%P==) {ans=ans*i%P;break;}

    cout<<ans;

    return ;

}