思路：首先是Burnside引理，要先学会这个博客。
Burnside引理我们总结一下，就是 每种置换下不动点的数量之和除以置换的总数，得到染色方案的数量。
这道题，显然每种洗牌方式都是一种置换，我们先数出每种置换的不动点。什么叫不动点，就是在这个置换下不停的变化后状态不变的染色方案。容易想出每个置换都有一个循环节，每张牌在某种洗牌方式下的位置是循环的，那要使得这个成为一个不动点，就需要使得同一循环节上的牌的颜色相同。那么这个问题就转化成了一个三维背包问题了。
背包的转移方程为$f[i][j][k]+=f[i-size][j][k]+f[i][j-size][k]+f[i][j][k-size]$。
接下来就是一个简单的逆元了，注意本身不动也是一种染色方案。
#include<bits/stdc++.h> #define clr(a,b) memset(a,b,sizeof(a)) #define fpn() freopen("simple.in","r",stdin) #define rd read() using namespace std; typedef long long ll; inline int read() { int x=0,t=1;char ch=getchar(); while((ch<‘0‘||ch>‘9‘)&&ch!=‘-‘)ch=getchar(); if(ch==‘-‘)t=-1,ch=getchar(); while(ch<=‘9‘&&ch>=‘0‘)x=x*10+ch-48,ch=getchar(); return x*t; } const int maxn=110; int p,a[maxn],vis[maxn],f[maxn][maxn][maxn],siz[maxn],tot; int sr,sb,sg,m,ans,n; int solve(){ clr(vis,0),clr(f,0),tot=0; int len=0; for(int i=1;i<=n;i++){ len=0; if(!vis[i]){ int k=i; while(!vis[k]){ len++; vis[k]=1; k=a[k]; } siz[++tot]=len; } } f[0][0][0]=1; for(int s=1;s<=tot;s++) { for(int i=sr;i>=0;i--) { for(int j=sb;j>=0;j--) { for(int k=sg;k>=0;k--) { if(i>=siz[s])f[i][j][k]=(f[i][j][k]+f[i-siz[s]][j][k])%p; if(j>=siz[s])f[i][j][k]=(f[i][j][k]+f[i][j-siz[s]][k])%p; if(k>=siz[s])f[i][j][k]=(f[i][j][k]+f[i][j][k-siz[s]])%p; } } } } return f[sr][sb][sg]; } int qpow(int a,int b){ int res=1; while(b){ if(b&1){ res*=a; res%=p; } b>>=1; a*=a; a%=p; } return res; } int main(){ cin>>sr>>sb>>sg>>m>>p; n=sr+sb+sg; for(int i=1;i<=n;i++)a[i]=i; int ans=0; ans+=solve()%p; for(int t=1;t<=m;t++) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } ans=(ans+solve())%p; } ans=ans*qpow(m+1,p-2)%p; cout<<ans<<endl; }
bzoj1004 [HNOI2008]Cards Burnside定理+背包
原文：https://www.cnblogs.com/mountaink/p/10439573.html
