「HNOI2008」洗牌cards - Polya计数+背包

题目大意

    小春现在很清闲,面对书桌上的$N$张牌,他决定给每张染色,目前小春只有$3$种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出$S_r$张红色,$S_b$张蓝色,$S_g$张绿色.他又询问有多少种方案,Sun想了一下,又给出了正确答案.
    最后小春发明了$M$种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以$P$的余数($P$为质数).

---

题目分析

本题给出了$m+1$个置换（$+1$的那个是不变的置换），要求染色，对颜色总数有限制，询问等价类个数。
根据Polya定理，将每个置换拆成不相交循环。
每个循环染同样的颜色，然后询问染色的数量。
因为限制的是颜色的总数目，故计数可以用背包来完成。

优化：背包可以省去一维，因为一旦确定两维，剩下一维一定确定。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>

using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(isdigit(x)) {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=25;

int R,B,G,n,m,p,a[maxn*3],f[maxn][maxn],ans=0;
bool vst[maxn*3];
vector<int> cir;

void add(int &x,int v) {
	x+=v;
	if(x>=p)x-=p;
}

int Quick_Pow(int a,int b) {
	int ans=1;
	for(; b; b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;
	return ans;
}

void Bag_Dp() {
	memset(f,0,sizeof(f));
	f[0][0]=1;
	for(int j=1; j<=cir.size(); j++) {
		int now=cir[j-1];
		for(int a=R; a>=0; a--)
			for(int b=G; b>=0; b--) {
				if(a>=now)add(f[a][b],f[a-now][b]);
				if(b>=now)add(f[a][b],f[a][b-now]);
			}
	}
	add(ans,f[R][G]);
}

int main() {
	R=Get_Int();
	G=Get_Int();
	B=Get_Int();
	m=Get_Int();
	p=Get_Int();
	n=R+G+B;
	for(int i=1; i<=m; i++) {
		fill(vst+1,vst+n+1,0);
		cir.clear();
		for(int j=1; j<=n; j++)a[j]=Get_Int();
		for(int j=1; j<=n; j++)
			if(!vst[j]) {
				int size=0;
				for(int k=j; !vst[k]; k=a[k])vst[k]=1,size++;
				cir.push_back(size);
			}
		Bag_Dp();
	}
	cir.clear();
	for(int i=1; i<=n; i++)cir.push_back(1);
	Bag_Dp();
	printf("%d\n",ans*Quick_Pow(m+1,p-2)%p);
	return 0;
}