P1446 [HNOI2008] Cards

如何处理带限制的 Pólya 定理？（每种颜色 $c_i$ 的数目固定为 $S_{c_i}$ ）

如果每个环的大小一致为 $s$ ，我们可以采取这样的方法：

若存在 $S_c \not\equiv 0 \pmod s$ ，那么说明无法分配，方案数为 $0$ 。
若不存在上述问题，就是多重集的排列数问题，方案数为：
$\binom{\sum S_{c_i}/s}{S_{c_1}/s,S_{c_2}/s,\cdots S_{c_n}/s}$

如果环的大小并无限制，这就需要我们使用动态规划。

显然每个环内染色的颜色必须一致，那么使得置换后颜色相同的染色方案数可以理解为将每个环的大小分配给 $r,b,g$ 三种颜色，求分配方案数，这就是一个典型的背包问题。

#include <bits/stdc++.h>
#define MAXS 25
#define MAXN 65
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int dp[MAXN][MAXS][MAXS][MAXS];
int mod;
int sz[MAXN],top;
int sr,sb,sg,n;
int fac[MAXN],invfac[MAXN];
int to[MAXN];
int ksm(int b,int k){
	int ans=1;
	while (k){
		if (k&1) ans=ans*b%mod;
		b=b*b%mod;
		k>>=1;
	}
	return ans;
}
void calc(){
	memset(dp,0,sizeof(dp));
	dp[0][0][0][0]=1;
	for (int p=1;p<=top;++p){
		for (int i=0;i<=sr;++i){
			for (int j=0;j<=sb;++j){
				for (int k=0;k<=sg;++k){
					if (i+sz[p]<=sr) (dp[p][i+sz[p]][j][k]+=dp[p-1][i][j][k])%=mod;
					if (j+sz[p]<=sb) (dp[p][i][j+sz[p]][k]+=dp[p-1][i][j][k])%=mod;
					if (k+sz[p]<=sg) (dp[p][i][j][k+sz[p]]+=dp[p-1][i][j][k])%=mod;
				}
			}
		}
	}
	//总共dp[top][sr][sb][sg]种方案
}
int vis[MAXN];
int main(){
	int m,tm;
	sr=read(),sb=read(),sg=read(),m=read(),mod=read();
	n=sr+sg+sb;
	fac[0]=1,invfac[0]=1;
	for (int i=1;i<MAXN;++i) fac[i]=(fac[i-1]*i)%mod,invfac[i]=ksm(fac[i],mod-2);
	tm=m;
	int ans=0;
	while (tm--){
		for (int i=1;i<=n;++i) to[i]=read();
		memset(vis,0,sizeof(vis));
		top=0;
		for (int i=1;i<=n;++i){
			if (!vis[i]){
				int p=i,cnt=0;
				while (cnt==0||p!=i) p=to[p],vis[p]=true,cnt++;
				sz[++top]=cnt;
			}
		}
		calc();
		(ans+=dp[top][sr][sb][sg])%=mod;
	}
	top=0;
	for (int i=1;i<=n;++i){
		sz[++top]=1;
	}
	calc();
	(ans+=dp[top][sr][sb][sg])%=mod;
	printf("%d\n",ans*ksm(m+1,mod-2)%mod);
	return 0;
}