BZOJ 1004

时间:2024-01-02 17:22:56

一道奇怪的数学题。为了这道题我看了很多题解,到底还是一知半解。。整个感觉就是上了一场数学课。

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 7
2 3 1
3 1 2 Output
--------------------------------------
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}$ (公式请自行脑补) 。这里的$a^{-1}$被称为是a酱模p酱下的逆元。 由于为了区分,我用了+来标记。事实上一般的,我们写作(S,*)运算简写为ab 这时我们再来看题目。
我们可以将每一种洗牌法定义为一个集合P中的元素E。 我们用一种表示法表示这些元素,比如样例中的第一种洗牌法为 |1 2 3|
E1=| |
|2 3 1| 第二种 |1 2 3|
E2=| |
|3 1 2|
这时通过置换运算*(即为先置换元素再连接置换操作),有
E1E2=
|1 2 3||1 2 3| |1 2 3||2 3 1| |1 2 3|
| || |=| || |=| |
|2 3 1||3 1 2| |2 3 1||1 2 3| |1 2 3| 注意 |1 2 3|
| | 是单位元
|1 2 3| 那么E1^{-1}=E2. 通过这些初步了解,我们发现,置换操作和这个集合的性质可以很方便的定义为一个群,即置换群 (P,*) 。 关于置换群: Wikipedia =>
=================================================
循环 对于置换群中的一个元素E,它是由一些循环组成的。
这里的循环指的是,我们的一种洗牌法将一个位置上的东西变换到另外一个位置上时,其中几个东西之间的置换路径形成了环。 比如对于E1,
1->2,2->3,3->1,我们记该变换为(123),即(123)一个循环
萌萌哒单位元酱的循环是
1->1,2->2,3->3,那么就记为(1)(2)(3),表示1一个循环,依此类推
=================================================
等价类 一个等价类F即是题目中所描述,通过一些(P,*)中的置换E是可以达到相同的样子的排列Kn的一堆。他们自己构成了一个(子)群。
题目的意图,就是求F的数目
=================================================
Burnside 引理 用|S|表示集合S中元素的个数,X〰G表示集合X在置换群G的作用下的等价类的集合。X^g表示在g作用下X中不变元素的个数。
1 / g \
|X〰G|=---- SUM | |X ||
|G| g of G \ /
=================================================
恩先写这些吧。。基本可以脑补完了。