P1446 [hnoi2008] cards (Burnside theorem + DP count)

Topic link

The question ：

To dye a deck of cards , Dyeing $S_r$ Zhang Hong ,$S_b$ Zhang Lan Lan ,$S_g$ Green Zhang . Now it is given $m$ A shuffle ( substitution ), When a deck of cards can pass through this $m$ A shuffle ( You can use a variety of washing methods , Each can be used multiple times ) When shuffled into another deck , Say the two sets of cards are the same . Ask how many different decks can be dyed .
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

Ideas ：

Obviously $Burnside$ The application of the theorem （ Whether it can be used is another matter ）.
The formula ：
$$N(G,C)=\frac{1}{|G|}\sum _{f\in G}C(f)$$ Simple Introduce this formula ,$G$ It's a permutation group ,$C$ It's a coloring set ,$C(f)$ It's replacement $f$ In the shading set $C$ The number of fixed points under .
As for the requirements of permutation group , Is not very good .
The words here ,$G$ Inside is , Unit replacement and $m$ Shuffle replacement . A coloring set is all the different permutations of three colors that satisfy the number of colors .

We consider counting the number of fixed points of a permutation .
And then you'll find out , A coloring that does not move under a displacement , Currently, only if the color in each loop section is the same . therefore , For each permutation , Find its cyclic section , And then use $dp$ Just count .

Code ：

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