#P8729. [2024年山东第三轮集训]六进制

    ID: 8800 传统题 1500ms 1024MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>线性代数与代数高斯消元组合数学CF3000数学矩阵模运算概率论数位DP

[2024年山东第三轮集训]六进制

A. 六进制

题目描述

小ωω在学生物,他学习到基因是 DNA 片段。

现在他得到了一个长度为 3n3n 的碱基对序列 ACTACT...ACT,这个片段由nn 个密码子 ACT 构成。 邪恶博士带着他的突变枪来捣乱了。这把突变枪非常强大,并且内置了mm 个程序,其中一个是故障程序,一旦运行就会让突变枪损坏。

其他的程序作用到碱基对序列上就会打乱这个序列。具体来说,程序包含nn 个长度为 33 的排列,第ii 个排列会作用在第 ii 个密码子上,使得s1s2s3s_{1}s_{2}s_{3} 变成sp1sp2sp3s_{p_{1}}s_{p_{2}}s_{p_{3}}。

突变枪每次运行都会独立等概率随机选取一个程序执行。 邪恶博士疯狂使用他的突变枪直到它坏了为止。

小 ω 很好奇最后碱基对序列变成每种样子的概率,答案对 998244353998244353 取模。

输入格式

从标准输入读入。 第一行一个整数nn 表示密码子个数。 第二行6n6^{n} 个整数cic_{i},表示某一种程序的个数,程序如下:

把i−1i-1表示为 nn 位 66 进制数 anan−1an−2⋯a1‾\overline{{a_{n} a_{n-1} a_{n-2} \cdots a_{1}}},aja_{j} 表示对第jj 个密码子的排列是字典序第 aj+1a_j+1 小的长为 33 的排列。

即 0⋯50\cdots 5 分别表示$( 1 , 2 , 3 ) , ( 1 , 3 , 2 ) , ( 2 , 1 , 3 ) , ( 2 , 3 , 1 ) , ( 3 , 1 , 2 ) , ( 3 , 2 , 1 )$。

前文说的 mm 等于 1+∑i=16nci1+\sum_{i=1}^{6^n}c_i。

输出格式

向标准输出写出。 为了减少输出量,你只需要输出所有答案的异或和即可。 如果存在一个答案在模 998244353998244353 意义下不收敛,输出−1-1。 否则输出一行一个整数表示最后碱基对序列变成每种样子的概率对 998244353998244353 取模后结果的异或和。

样例 1

样例1输入

1
0 0 0 1 0 0

样例1输出

1

样例 1 解释

突变枪内置了两种程序,一种是故障程序,一种对应排列(2,3,1)(2,3,1)。 最后序列为 ACT 的概率为4/74/7,取模后为427819009427819009。 最后序列为 CTA 的概率为 2/72/7,取模后为 713031681713031681。 最后序列为 TAC 的概率为 1/71/7,取模后为 855638017855638017。 三者异或和为 11。

数据范围与提示

对于所有数据,保证 1≤n≤81\le n\le 8,mm 不是 998244353998244353 的整数倍,ci∈[0,998244353)c_{i}\in [0,998244353)。

子任务编号 子任务分值 nn 特殊性质
1 7 =1=1
2 =2=2
3 =3=3
4 =4=4
5 12 =5=5
6 =6=6
7 =7=7 如果 ci≠0c_{i}\ne 0,则 i−1i-1 的 66 进制表示只包含 0,3,40,3,4
8 =8=8
9 =7=7
10 =8=8

表中程序编码统一使用 i−1i-1,与输入格式一致:编码数位 0,3,40,3,4 对应三个偶排列。