[HNOI2008] Cards

题目链接：戳我

看落咕上有一些题解用公式把题做出来了，我也不会这种数论方法，（而且好像是解法被hack了

这里介绍burnside+dp的做法。

设dp[i][j][k]表示对于当前这种置换，三种颜色分别使用i,j,k个的染色方案个数。转移的话，我们将置换拆成循环，要从上一个没有使用这种颜色染色这个循环的方案数转移过来（一个循环中涉及到的卡牌必须都染成同一种颜色嘛。。。要不然还怎么是不动点qwq）——要么将当前这个循环用该颜色染色，要么不染该循环。而循环之间因为互不影响，所以可以累加计数。

转移过程有点01背包思想。

emmmm之后还想解释两点：一个是转移的时候为什么第三种颜色不能表示成n-i-j。这个是因为既然是DP，就要考虑完所有的情况。可能不需要总数达到n就可以获得新的染色方案数量，就是背包思想。二是数量从大到小转移。因为一个循环不能用同一种颜色染两次，就是不能叠加，所以就是类似于01背包，而不是完全背包，所以要从大到小。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 65
using namespace std;
int sum1,sum2,sum3,m,p,n,tot,ans;
int trans[MAXN][MAXN],dp[MAXN][MAXN][MAXN],cnt[MAXN],done[MAXN];
inline int pow(int x,int y)
{
    int cur_ans=1;
    while(y)
    {
        if(y&1) cur_ans=cur_ans*x%p;
        x=x*x%p;
        y>>=1;
    }
    return cur_ans%p;
}
inline int solve(int x)
{
    memset(dp,0,sizeof(dp));
    memset(done,0,sizeof(done));
    memset(cnt,0,sizeof(cnt));
    tot=0;
    for(int i=1;i<=n;i++)
    {
        if(done[i]) continue;
        done[i]=1,cnt[++tot]=1;
        int now=trans[x][i];
        while(!done[now]){cnt[tot]++,done[now]=1,now=trans[x][now];}
    }
    dp[0][0][0]=1;
    for(int t=1;t<=tot;t++)
        for(int i=sum1;i>=0;i--)
            for(int j=sum2;j>=0;j--)
                for(int k=sum3;k>=0;k--)
                {
                    if(i>=cnt[t]) dp[i][j][k]=(dp[i][j][k]+dp[i-cnt[t]][j][k])%p;
                    if(j>=cnt[t]) dp[i][j][k]=(dp[i][j][k]+dp[i][j-cnt[t]][k])%p;
                    if(k>=cnt[t]) dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-cnt[t]])%p;
                }
    return dp[sum1][sum2][sum3];
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    scanf("%d%d%d%d%d",&sum1,&sum2,&sum3,&m,&p);
    n=sum1+sum2+sum3;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&trans[i][j]);
    for(int i=1;i<=n;i++) trans[m+1][i]=i;
    for(int i=1;i<=m+1;i++)
        ans=(ans+solve(i))%p;
    ans=1ll*ans*pow(m+1,p-2)%p;
    printf("%d
",ans%p);
}