BZOJ1004 - Click Here
Description
小春现在很清闲，面对书桌上的N张牌，他决定给每张染色，目前小春只有3种颜色：红色，蓝色，绿色。他询问Sun有多少种染色方案，Sun很快就给出了答案。进一步，小春要求染出Sr张红色，Sb张蓝色，Sg张绝色。他又询问有多少种方案，Sun想了一下，又给出了正确答案。 最后小春发明了M种不同的洗牌法，这里他又问Sun有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法，而每种方法可以使用多次)洗成另一种。Sun发现这个问题有点难度，决定交给你，答案可能很大，只要求出答案除以P的余数(P为质数)。
Input
第一行输入 5 个整数：Sr,Sb,Sg,m,p(m<=60,m+1<p<100)。n=Sr+Sb+Sg。
接下来 m 行，每行描述一种洗牌法，每行有 n 个用空格隔开的整数 X1X2…Xn，恰为 1 到 n 的一个排列，表示使用这种洗牌法，第i位变为原来的Xi位的牌。输入数据保证任意多次洗牌都可用这m种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。
Output
不同染法除以P的余数
Solutions
这题大概要理解Polya定理才能切掉？
题目给出了若干个置换，而且保证了这些置换成群。
如果不存在颜色限制的话，就是一个裸的Polya应用。
现在考虑如何处理颜色限制。
注意到，Polya定理实际上是Burnside引理从另外一个角度考虑的式子，其实质是对于每个循环保证颜色相同，对应到Burnside里的一个不动点。
因此，虽然有颜色限制，但只要保证每个循环颜色相同即可。
这是一个经典的背包问题，可以直接DP出来。
时间复杂度$O(mn^3)$
CODE
CODE - Click Here