#P8729. [2024年山东第三轮集训]六进制
[2024年山东第三轮集训]六进制
A. 六进制
题目描述
小在学生物,他学习到基因是 DNA 片段。
现在他得到了一个长度为 的碱基对序列 ACTACT...ACT,这个片段由 个密码子 ACT 构成。 邪恶博士带着他的突变枪来捣乱了。这把突变枪非常强大,并且内置了 个程序,其中一个是故障程序,一旦运行就会让突变枪损坏。
其他的程序作用到碱基对序列上就会打乱这个序列。具体来说,程序包含 个长度为 的排列,第 个排列会作用在第 个密码子上,使得 变成。
突变枪每次运行都会独立等概率随机选取一个程序执行。 邪恶博士疯狂使用他的突变枪直到它坏了为止。
小 ω 很好奇最后碱基对序列变成每种样子的概率,答案对 取模。
输入格式
从标准输入读入。 第一行一个整数 表示密码子个数。 第二行 个整数,表示某一种程序的个数,程序如下:
把表示为 位 进制数 , 表示对第 个密码子的排列是字典序第 小的长为 的排列。
即 分别表示$( 1 , 2 , 3 ) , ( 1 , 3 , 2 ) , ( 2 , 1 , 3 ) , ( 2 , 3 , 1 ) , ( 3 , 1 , 2 ) , ( 3 , 2 , 1 )$。
前文说的 等于 。
输出格式
向标准输出写出。 为了减少输出量,你只需要输出所有答案的异或和即可。 如果存在一个答案在模 意义下不收敛,输出。 否则输出一行一个整数表示最后碱基对序列变成每种样子的概率对 取模后结果的异或和。
样例 1
样例1输入
1
0 0 0 1 0 0
样例1输出
1
样例 1 解释
突变枪内置了两种程序,一种是故障程序,一种对应排列。 最后序列为 ACT 的概率为,取模后为。 最后序列为 CTA 的概率为 ,取模后为 。 最后序列为 TAC 的概率为 ,取模后为 。 三者异或和为 。
数据范围与提示
对于所有数据,保证 , 不是 的整数倍,。
| 子任务编号 | 子任务分值 | 特殊性质 | |
|---|---|---|---|
| 1 | 7 | ||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | 12 | ||
| 6 | |||
| 7 | 如果 ,则 的 进制表示只包含 | ||
| 8 | |||
| 9 | |||
| 10 |
表中程序编码统一使用 ,与输入格式一致:编码数位 对应三个偶排列。