#P1446. [HNOI2008] Cards

    ID: 490 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp数论数学置换逆元各省省选2008湖南

[HNOI2008] Cards

题目描述

小春现在很清闲,面对书桌上的 nn 张牌,他决定给每张牌染色,目前小春拥有 33 种颜色:红色,蓝色,绿色。他询问 Sun 有多少种染色方案,Sun 很快就给出了答案。

进一步,小春要求染出 SrS_r 张红色,SbS_b 张蓝色,SgS_g 张绿色。他又询问有多少种方案,Sun 想了一下,又给出了正确答案。最后小春发明了 mm 种不同的洗牌法,这里他又问 Sun 有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种。

Sun 发现这个问题有点难度,决定交给你,由于答案可能很大,你只需要求出答案对于 PP 取模的结果。 保证 PP 为一个质数。

输入格式

第一行输入 55 个整数,依次表示:Sr,Sb,Sg,m,PS_r,S_b,S_g,m,Pm60,m+1<p<100m\le 60,m+1<p<100)。其中,题面所提及的 nnSr+Sb+SgS_r+S_b+S_g,即 n=Sr+Sb+Sgn=S_r+S_b+S_g

接下来 mm 行,每行描述一种洗牌法,每行有 nn 个用空格隔开的整数 X1X2...XnX_1X_2...X_n,保证其为 11nn 的一个排列,表示使用这种洗牌法,第 ii 位变为原来的 XiX_i 位的牌。输入数据保证任意多次洗牌都可用这 mm 种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。

同时,对于 100%100\% 的数据满足 max{Sr,Sb,Sg}20\max\{S_r,S_b,S_g\}\le 20

输出格式

不同的染色方法对 PP 取模的结果。

1 1 1 2 7
2 3 1
3 1 2
2

提示

22 种本质上不同的染色法:RGBRBG,使用洗牌法 231 一次,可得 GBRBGR,使用洗牌法 312 一次,可得 BRGGRB