luogu P1446 [HNOI2008]Cards

题目链接

luogu P1446 [HNOI2008]Cards

题解

题意就是求染色方案->等价类

洗牌方式构成成了一个置换群

然而,染色数限制不能用polay定理直接求解

考虑burnside引理

对于一个置换群其等价类的个数为置换中不动点的平均数

先暴力求出置换中的轮换，然后01背包DP求出不动点方案数

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using std::__gcd;

#define LL long long

const int maxn = 70;

inline int read() {

    char c=getchar();int x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();

    return x;

}

int sr,sb,sg,m,p,n,cnt;

bool vis[maxn],size[maxn*maxn];

int col[maxn],f[maxn][maxn][maxn];

inline void find() {//找到该置换中轮换的个数

    cnt=0;

    memset(vis,0,sizeof vis);

    memset(size,0,sizeof col);

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

        if(!vis[i]) {

            int p=i;cnt++;

            while(!vis[p])vis[p]=1,size[cnt]++,p=col[p];

        }

    }

}

int count() {

    memset(f,0,sizeof f);

    f[0][0][0]=1;

    for(int q=1;q<=cnt;++q)

        for(int i=sr;i>=0;--i)

            for(int j=sb;j>=0;--j)

                for(int k=sg;k>=0;--k) {

                    if(i>=size[q]) f[i][j][k]=(f[i][j][k]+f[i-size[q]][j][k])%p;

                    if(j>=size[q]) f[i][j][k]=(f[i][j][k]+f[i][j-size[q]][k])%p;

                    if(k>=size[q]) f[i][j][k]=(f[i][j][k]+f[i][j][k-size[q]])%p;

                }

    return f[sr][sb][sg];

}

LL qpow(int x,int q) {

    int ret=1;

    for(int i=q;i;i>>=1,x=x*x%p)

        if(i&1)ret=ret*x%p;

    return ret;

}

int main() {

    LL ans=0;

    sr=read(),sb=read(),sg=read(),m=read(),p=read();

    n=sr+sb+sg;

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

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

            col[j]=read();

        }

        find();

        ans+=count();

    }

    //m+1为不动置换

    for(int i=1;i<=n;++i) col[i]=i;

    find();

    ans+=count();

    ans=(ans*qpow(m+1,p-2))%p;

    std::cout<<ans<<std::endl;

    return 0;

}