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\) 的余数
Sample Input
1 1 1 2 7
2 3 1
3 1 2
Sample Output
2
HINT
有 \(2\) 种本质上不同的染色法 \(RGB\) 和 \(RBG\)，使用洗牌法 \(231\) 一次可得 \(GBR\) 和 \(BGR\) ，使用洗牌法 \(312\) 一次 可得 \(BRG\) 和 \(GRB\)。
\(100%\) 数据满足 \(Max{Sr,Sb,Sg} \leq 20\)。想法
该题为 \(Burnside\) 引理的典型应用题。
预备知识
置换：在集合论中，一个集合的置换是从该集合映至自身的双射。
它是一种运算
置换群：n元对称群的任意一个子群,都叫做一个n元置换群,简称置换群。
简单来说，就是若干置换组成的集合，且满足“群”的特点，即：
\(i)\) 封闭性：置换群 \(G\) 中任意两个置换结合形成的置换在 \(G\) 中\(ii)\) 结合性：（\(a\) 结合 \(b\)） 结合 \(c\) \(=\) \(a\) 结合 （\(b\) 结合 \(c\)）\(iii)\) 单位元： \(G\) 中存在置换 \(e\) 满足 \(e\) 与 \(G\) 中任意置换 \(a\) 结合，结果为 \(a\) （即 \(e\) 为单位元）\(iiii)\) 逆元： 对 \(G\) 中任意置换 \(a\) ，\(G\) 中都存在置换 \(b\) 使 \(a\) 与 \(b\) 结合后结果为 \(e\)等价类 ：某个序列 \(A\) 经过 \(G\) 中的某个置换变成 \(B\)， 则 \(A\) 与 \(B\) 属于同一等价类
不动点： 若一个序列 \(A\) 经过置换 \(a\) 后仍为 \(A\) , 则称 \(A\) 为置换 \(a\) 的不动点Burnside引理
设置换群 \(G\) 为等价关系集合，\(C(f)\) 表示置换 \(f\) 的不动点个数。
则等价类个数 \(L=\frac{\sum{C(f)}}{|G|}\)
证明不会。。。先记住就好
计算不动点个数
其实每个置换可以写成若干个循环乘积形式
如置换 \(2 4 5 1 3\) 中，其实只有 \(1,2,4\) 互换位置， \(3,5\) 互换位置，故可以写成：\((1,2,4) \cdot (3,5)\)
在染色问题中， 若要经过一次置换后仍不变，则\(1,2,4\) 必须同色， \(3,5\) 必须同色，而这两者之间颜色互不干扰。
故这个置换的不动点个数为 \(颜色数 ^ 2\)\(\Rightarrow\) 设颜色数为 \(m\) , 某一个置换有 \(x\) 个循环节，则该置换的不动点个数为 \(m^x\)Polya定理
其实就是上面的 \(Burnside\) 引理与 计算不动点个数的结合，专门针对染色问题。
设 \(G\) 是 \(n\) 个对象的一个置换群, 用 \(m\) 种颜色染图这 \(n\) 个对象，则不同的染色方案数为：
\(L=\frac{\sum{m^{C(f)}}}{|G|}\) 注意在这里面 \(C(f)\) 表示置换 \(f\) 的循环节数。
小例题
有一个圆形项链，上面有 \(n\) 个珠子，这 \(n\) 个珠子由 \(m\) 中颜色组成。经过旋转后（不是翻转！）相同的项链为相同的项链，请问一共有多少不同的项链？
解法： 本题中的置换群为\[ \left\{ \begin{matrix} 1 & 2 & 3 & … & n\\ 2 & 3 & … & n & 1 \\ … & … & … & … & …\\ n & 1 & 2 & 3 & … \end{matrix} \right\} \] 我们管这个置换群中的置换形象地叫做“转圈圈置换” 则置换群中第 \(i\) 个置换（顺序见上），它的循环节数为 \(gcd(i,n)\) 应用 \(Polya\) 定理既可做出来。本题解法！！！
题中所说的洗牌法基本满足置换群性质，只要加上单位元就是真正的置换群了！
为了套用定理，我们要考虑如何计算不动点个数。 如果没有对 \(RGB\) 数量的限制，那暴力找循环就可以了然后套 \(Polya\) 定理就行了。 但有限制咋办呢？ ——还是暴力找循环，记下每个环的大小。 由于每个环上点必须是同一颜色，问题转化为把环扔进3个大小有限制的背包中，求放法。\(DP\) 就好啦。代码
#include#include #include #include using namespace std; const int N = 65;typedef long long ll; int sr,sb,sg,m,n,P;int cg[N][N]; int Pow_mod(int x,int y){ int ret=1; while(y){ if(y&1) ret=((ll)ret*x)%P; x=((ll)x*x)%P; y>>=1; } return ret;} int cnt[N],t;int vis[N],f[25][25][25]; int main(){ scanf("%d%d%d%d%d",&sr,&sb,&sg,&m,&P); n=sr+sb+sg; for(int i=0;i