M_sea

洛谷1446 [HNOI2008]Cards
Luogu分析把每种洗牌法看成一个置换,那么题目就是等价类计数。考虑 Burnside 引理。我们只需要求出每个置...
扫描右侧二维码阅读全文
03
2019/09

洛谷1446 [HNOI2008]Cards

Luogu

分析

把每种洗牌法看成一个置换,那么题目就是等价类计数。

考虑 Burnside 引理。我们只需要求出每个置换的不动点个数即可。

考虑把置换拆成循环乘积的形式。对于一种不动点,显然一个循环内的颜色是相同的。

于是可以考虑 DP 。设 $dp_{i,r,g,b}$ 表示前 $i$ 个循环,涂了 $r$ 个红色、$g$ 个绿色、$b$ 个蓝色的方案数,转移就是 01 背包。

另外要自行加上单位置换,也就是说置换的总数是 $m+1$ 而不是 $m$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=60+10,S=20+10;

int n,m,Sr,Sb,Sg,mod,ans=0;
int p[N],vis[N],sz[N],tot=0;
int dp[N][S][S][S];

inline void add(int& x,int y) { x=(x+y)%mod; }
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=a*a%mod) if (b&1) c=c*a%mod;
    return c;
}

inline int calc() {
    memset(vis,0,sizeof(vis)),memset(sz,0,sizeof(sz)),tot=0;
    for (re int i=1,j;i<=n;++i) {
        if (vis[i]) continue;
        ++tot,j=i;
        while (!vis[p[j]]) vis[p[j]]=1,j=p[j],++sz[tot];
    }
    memset(dp,0,sizeof(dp)); dp[0][0][0][0]=1;
    for (re int i=1;i<=tot;++i)
        for (re int r=0;r<=Sr;++r)
            for (re int g=0;g<=Sg;++g)
                for (re int b=0;b<=Sb;++b) {
                    if (r>=sz[i]) add(dp[i][r][g][b],dp[i-1][r-sz[i]][g][b]);
                    if (g>=sz[i]) add(dp[i][r][g][b],dp[i-1][r][g-sz[i]][b]);
                    if (b>=sz[i]) add(dp[i][r][g][b],dp[i-1][r][g][b-sz[i]]);
                }
    return dp[tot][Sr][Sg][Sb];
}

int main() {
    n=((Sr=read())+(Sb=read())+(Sg=read())),m=read(),mod=read();
    for (re int i=1;i<=m;++i) {
        for (re int j=1;j<=n;++j) p[j]=read();
        add(ans,calc());
    }
    for (re int i=1;i<=n;++i) p[i]=i;
    add(ans,calc());
    printf("%d\n",ans*qpow(m+1,mod-2)%mod);
    return 0;
}
最后修改:2019 年 09 月 03 日 08 : 29 PM

发表评论