思路：首先是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;
}
View Code