题意理解

我们有一个由 $n$ 个密码子 "ACT" 组成的 DNA 序列，总长度为 $3n$。

突变枪有 $m$ 个程序：

• 1 个故障程序（使枪损坏）
• $m-1$ 个正常程序，每个程序由 $n$ 个长度为 3 的排列组成

每个程序的作用是：对第 $i$ 个密码子施加第 $i$ 个排列变换。

突变枪每次随机选择一个程序执行，直到选中故障程序为止。

我们需要求最终序列变成每种可能序列的概率。

核心思路

关键观察 1：问题结构分析

这是一个马尔可夫过程：

• 状态：所有可能的 $6^n$ 种序列（每个密码子有 6 种排列）
• 转移：通过执行程序进行状态转移
• 终止条件：选中故障程序

关键观察 2：概率模型

设 $P$ 是转移概率矩阵，$p_f = \frac{1}{m}$ 是选中故障程序的概率。

最终状态分布向量 $\vec{\pi}$ 满足：

$$\vec{\pi} = p_f \cdot (I + P + P^2 + \cdots) \cdot \vec{\pi}_0 $$

其中 $\vec{\pi}_0$ 是初始状态分布（集中在 "ACT ACT ... ACT"）。

由于 $p_f > 0$，这个几何级数收敛到：

$$\vec{\pi} = p_f \cdot (I - P)^{-1} \cdot \vec{\pi}_0 $$

关键观察 3：群作用与表示论

所有程序构成一个群作用：

• 每个程序对应 $S_3^n$ 中的一个元素
• 状态空间是 $S_3^n$ 在序列空间上的群表示

我们可以利用群表示论来分解问题。

算法框架

方法一：高维快速沃尔什-哈达玛变换

由于每个密码子的变换是独立的，问题在 $n$ 个维度上可分离。

定义 $6 \times 6$ 的转移矩阵 $T$，其中 $T_{i,j}$ 表示从排列 $i$ 经过一次随机程序变为排列 $j$ 的概率。

那么整个系统的转移矩阵是 $T^{\otimes n}$（$n$ 阶张量积）。

方法二：生成函数与卷积

对于每个密码子位置，我们可以用生成函数表示转移概率。

设 $f_i(x)$ 表示第 $i$ 个密码子的转移生成函数，那么整个系统的生成函数是：

$$F(x_1, \dots, x_n) = \prod_{i=1}^n f_i(x_i)$$

使用高维 FFT/NTT 在 $6^n$ 维空间中进行变换。

方法三：矩阵求逆的优化

我们需要计算 $(I - P)^{-1}$，其中 $P$ 是 $6^n \times 6^n$ 矩阵。

利用张量积结构：

$$(I - P) = \bigotimes_{i=1}^n (I - T_i)$$

因此：

$$(I - P)^{-1} = \bigotimes_{i=1}^n (I - T_i)^{-1}$$

这将 $6^n \times 6^n$ 的矩阵求逆转化为 $n$ 个 $6 \times 6$ 矩阵求逆。

具体实现分析

步骤 1：构建单密码子转移矩阵

对于每个密码子位置 $i$，构建 $6 \times 6$ 转移矩阵 $T_i$：

$$(T_i)_{j,k} = \frac{\text{程序集中使得第 } i \text{ 个密码子从排列 } j \text{ 变为 } k \text{ 的程序数}}{m-1} $$

步骤 2：求解单密码子稳态分布

对于每个密码子，求解：

$$\vec{\pi}_i = p_f \cdot (I - T_i)^{-1} \cdot \vec{e}_{\text{初始}} $$

其中 $\vec{e}_{\text{初始}}$ 是初始状态（对应排列 0）。

步骤 3：组合所有密码子

由于各密码子独立，最终概率分布是各密码子分布的乘积：

$$P(\text{最终序列}) = \prod_{i=1}^n P(\text{第 } i \text{ 个密码子的最终排列}) $$

步骤 4：处理收敛性

当且仅当每个 $I - T_i$ 都可逆时，答案收敛。

根据 Perron-Frobenius 理论，这等价于 Markov 链的不可约性和非周期性。

复杂度分析

直接暴力：$O(6^{3n})$，不可行

张量积方法：

• 构建单密码子矩阵：$O(n \cdot 6^2)$
• 单矩阵求逆：$O(6^3)$
• 总复杂度：$O(n \cdot 6^3 + 6^n)$

对于 $n \leq 8$，$6^8 = 1679616$ 是可接受的。

特殊性质处理

特殊性质 A

当 $c_i \neq 0$ 时，$i$ 的 6 进制表示只包含 ${0,3,4}$。

这意味着只有特定的排列组合出现，可以进一步简化状态空间。

实现细节

模运算处理

• 模数 $998244353$ 是 NTT 友好质数
• 需要计算矩阵逆，使用高斯消元法
• 注意除法要转换为模逆元

张量积计算

使用递归或迭代方式计算高维张量积，避免显式构造大矩阵。

输出优化

由于只需要输出异或和，可以在计算过程中逐步累积，避免存储所有 $6^n$ 个概率值。

总结

本题的核心在于：

1. 概率模型：将问题建模为吸收 Markov 链
2. 代数结构：利用群作用和张量积分解问题
3. 算法优化：通过高维 FFT/NTT 和矩阵分解降低复杂度
4. 数学理论：结合表示论、线性代数和概率论

这是一个典型的高维生成函数 + 矩阵计算问题，考察选手对代数结构和概率模型的深入理解。