P1446 [HNOI2008]Cards（Burnside定理+dp计数）

题目链接

题意：

要给一副牌染色，染成$S_r$张红色，$S_b$张蓝色，$S_g$张绿色。现给出了$m$种洗牌法(置换)，当一副牌可以通过这$m$种洗牌法 (可以用多种洗法，每种可以用多次)洗成另一副牌时，则称这两副牌是同一种。问能染出多少种不同副牌。
m a x { S r , S b , S g } ≤ 20 , m ≤ 60 max\{S_{r},S_{b},S_{g}\}\leq20,m\leq60 max{ Sr​,Sb​,Sg​}≤20,m≤60

思路：

显然是$Burnside$定理的运用（会不会用是另一回事）。
公式：
$$N(G,C)=\frac{1}{|G|}\sum _{f\in G}C(f)$$简单 介绍一下这个公式，$G$是置换群，$C$是着色集，$C(f)$是置换$f$在着色集$C$下的不动点数。
至于置换群要符合的要求，不是很懂。
这里的话，$G$里面的是，单位置换和$m$种洗牌置换。着色集就是满足数量的三种颜色的所有不同排列。

我们考虑统计某个置换的不动点数。
然后会发现，一种着色在某个置换下不动，当前仅当每个循环节中的颜色相同。所以，我们对于每个置换，求出它的循环节，然后用$dp$计数就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int Sr,Sb,Sg,m,p;
int n;
int a[105];

int flag[105];
int dp[30][30][30];
int getC()
{
    
    memset(flag,0,sizeof(flag));
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)if(!flag[i])
    {
    
        int now=i;
        flag[now]=1;
        int num=1;
        while(!flag[a[now]])
        {
    
            num++;
            now=a[now];
            flag[now]=1;
        }
        for(int r=Sr;r>=0;r--)
        {
    
            for(int b=Sb;b>=0;b--)
            {
    
                for(int g=Sg;g>=0;g--)
                {
    
                    if(r>=num)dp[r][b][g]=(dp[r][b][g]+dp[r-num][b][g])%p;
                    if(b>=num)dp[r][b][g]=(dp[r][b][g]+dp[r][b-num][g])%p;
                    if(g>=num)dp[r][b][g]=(dp[r][b][g]+dp[r][b][g-num])%p;
                }
            }
        }
    }
    return dp[Sr][Sb][Sg];
}

int fpow(int a,int n,int p)
{
    
    int sum=1,base=a;
    while(n!=0)
    {
    
        if(n%2)sum=sum*base%p;
        base=base*base%p;
        n/=2;
    }
    return sum;
}

int main()
{
    
    scanf("%d%d%d%d%d",&Sr,&Sb,&Sg,&m,&p);
    n=Sr+Sb+Sg;
    int ans=0;
    for(int i=1;i<=n;i++)a[i]=i;
    ans=(ans+getC())%p;
    for(int i=1;i<=m;i++)
    {
    
        for(int j=1;j<=n;j++)scanf("%d",&a[j]);
        ans=(ans+getC())%p;
    }
    printf("%d\n",ans*fpow(m+1,p-2,p)%p);
    return 0;
}