Description
小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答 案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案.
最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用 多种洗牌法,而每种方法可以使用多次)洗成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).
第一行输入五个整数:Sr,Sb,Sg,M,P(M<=60,M+1
<100).
N=Sr+Sb+Sg.接下来M行,每行描述一种洗牌法,每行有N个用空格隔开的整数X1X2...Xn.
恰为1到N的一个排列,表示使用这种洗牌法,第I位变成原来的Xi位的牌.
输入数据保证任意多次洗牌都可以用M种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到
原状态.
20%的数据保证Sr+Sb+Sg<=20
100%的数据保证Max(Sr,Sb,Sg)<=20
Input
第一行输入五个整数:Sr,Sb,Sg,M,P(M<=60,M+1
<100).N=Sr+Sb+Sg.
接下来M行,每行描述一种洗牌法,每行有N个用空格隔开的整数X1X2...Xn.
恰为1到N的一个排列,表示使用这种洗牌法,第I位变成原来的Xi位的牌.
输入数据保证任意多次洗牌都可以用M种洗牌法中的一种代替,且对每种洗牌法
都存在一种洗牌法使得能回到原状态.
20%的数据保证Sr+Sb+Sg<=20
100%的数据保证Max(Sr,Sb,Sg)<=20
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。
我做这道题的时候,不知道什么是Polya和Burnside,于是学了N多数学知识……学完发现原来这题只是一道基础题……
我来上一堂数学课吧。
【群】给定一个集合G={a,b,c,…}和集合G上的二元运算*,并满足:
1.封闭性:对于所有的a,b∈G,存在一个c∈G,使得a*b=c
2.结合律:对于所有的a,b,c∈G,满足(a*b)*c=a*(b*c)
3.单位元:存在e∈G,对于所有的a∈G,满足a*e=e*a=a
4.逆元:对于所有a∈G,存在b∈G,a*b=b*a=e,记作
则称集合G在运算“*”之下是一个群,记作(G,*)。一般a*b简写成ab。
呃……简单来说群就是集合加运算符。比如(有理数集,+)就是一个群,念作有理数加法群。
不懂可以问维基,似乎说得挺清楚:http://en.wikipedia.org/wiki/Group_(mathematics)
【置换】n个元素1,2,…,n之间的一个置换为
表示1被1到n中某个数a1取代,2被1到n中某个数a2取代……n被1到n中某个数an取代。(a1、a2、a3…an互不相同)
举个例子:
这是一个置换。1 2 3 4 5经过置换后变成2 5 4 3 1。而9 0 1 4 5经过置换后变成0 5 4 1 9。
不懂可以问维基,似乎说得挺清楚:http://en.wikipedia.org/wiki/Permutation
【置换群】置换群的元素是置换,运算是置换的连接。例如:
置换群的封闭性和逆元会在题目中强调(不然就是不可捉题……),结合律嘛……哎呀……好像是显然耶……,单位元是,这家伙叫做恒等置换。
【循环】呃……这里的循环不是for啊,while啊那两个老家伙……呃……我语文不好……说不清楚定义……我就说我的理解吧……
想象一个N个节点的图,对于一个置换s,如果第i个元素经过置换后变为了第j个元素,那么就把第i号点和第j号点相连。发现了什么?形成了许多环对不对!那就叫循环。一个置换可以表示成若干个不相交的循环。比如:可以用循环表示成:(125)(34),就是刚才所说图中,1、2、5号点成一个环,3、4成一个环。表示一个循环时,(345) ≠ (435),但(345) = (453)(这个能理解吧……)。刚才所说的那个置换,既可以表示成(125)(34),也可以表示成(34)(125)。
好,现在Burnside引理闪亮登场……这个引理的中文名叫伯恩赛德引理。
不多说,先上公式:
等式左边表示置换群G在有限集合X作用下等价类的数目(如本题中的本质不同的方案数),等式右边是指(sum(经g的狂风骤雨般变幻后,X中仍旧不改变的元素的个数) (g∈G) ) ÷ G中元素的个数。好吧……这句话有点绕……我们记X中经过G[i]的作用后仍旧为没有变化的元素个数为d(i),比如X中若有元素(红,红,蓝),那么置换(12)(3)想把它变个样子,是不可能的,因为红与红交换仍然是红和红,miss了……而(红,蓝,黄)则瞬间被置换(123)秒杀成(蓝,黄,红)……变得不成样子了。那么置换群G在有限集合X作用下等价类的数目等于d(1),d(2),d(3)...d(n)的平均数。(n为G中元素的个数)啊啊啊啊啊……我也不知道我说清楚没……没看懂的见谅……
那么,对于本题,洗牌法就是咱们的置换,依据题目的特殊条件(题目中强调了群的封闭性和逆元,衡阳八中坑爹,题目不打全……),我们可以把所有洗牌法构成一个置换群,然后用上面的公式来求解。
好像有公式就万能了耶……这道题就可以水过了耶……
其实咱们忽略的一个挺烦人的函数:d(i)。咱们是要求G中所有置换的d值的平均值,但是d怎么求呢?
答案就是……DP……具体见http://hi.baidu.com/aekdycoin/blog/item/4f66126149ba5b4febf8f8bd.html吧……
AekdyCoin说要用乘法逆元……我表示我完全没有用诶……我定义了一个struct叫tempint,记录商和余数,然后各种YY……详见代码……
代码:(小心观看!)
#include <iostream>
评论