P1446 [HNOI2008]Cards(Burnside定理+dp计数)

  • 时间:
  • 浏览:
  • 来源:互联网

题目链接

题意:

要给一副牌染色,染成SrS_{r}张红色,SbS_{b}张蓝色,SgS_{g}张绿色。现给出了mm种洗牌法(置换),当一副牌可以通过这mm种洗牌法 (可以用多种洗法,每种可以用多次)洗成另一副牌时,则称这两副牌是同一种。问能染出多少种不同副牌。
max{Sr,Sb,Sg}20,m60max\{S_{r},S_{b},S_{g}\}\leq20,m\leq60

思路:

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

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

代码:

#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;
}

本文链接http://element-ui.cn/article/show-110848.aspx