首页 > 代码库 > BZOJ 1004
BZOJ 1004
一道奇怪的数学题。为了这道题我看了很多题解，到底还是一知半解。。整个感觉就是上了一场数学课。
HNOI2008 Cards
题目描述
小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案. 最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种.Sun发现这个问题有点难度,决定交给你,答案可能很大,只要求出答案除以P的余数(P为质数).
题目输入
第一行输入 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种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。
题目输出
一行一个数，即不同的染色方案数(mod p);
样例
Input--------------------------------------1 1 1 2 72 3 13 1 2Output--------------------------------------2
题解部分
首先说明一点，其实出题人是很良心的。 等你看完了题解后就知道我为什么这么说了。
首先，让我们引入一些数学概念。
群群是一种数学结构，可以理解为一个集合 S 和一个双目运算符 + 的二元组(S,+)需要满足以下条件: 1. 对于任何两个 S 中的元素，姑且记为 E1 和 E2 , E1 + E2 = E3 ,则 E3 也是 S 中的元素。 (比如说有理数集 R 与乘法运算符 × 构成了一个群，记为 (R,×), 任意两个有理数相加和都是有理数) 2. 结合律。回想一下，a+(b+c)=(a+b)+c，这就是结合律。 3. 单位元。设 (S,+) 的单位元为 U ,那么对于所有 S 中的 E1 , 有 E1 + U = U + E1 = E1 //这显然对于整数集有些奇怪，按照定义这里的 U = 0 。但是这里的符号 + 只是一个双目运算符的象征。 4. 逆元。回想一下同余中的 $aa^{-1}\equiv 1 \pmod{p}$ BZOJ 1004
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。