经过抽象并推广的谜题模型

谜题

$a_1,a_2,\dots,a_n$ 是整数变量（模 $m$ 剩余类）。$P_1,P_2,\dots,P_k$ 为 $k$ 个操作，操作 $P_i$ 使 $a_1,a_2,\dots,a_n$数值分别增加 $P_{i1},P_{i2},\dots,P_{in}$。$(i=1,2,\dots,k)$ （模 $m$ 意义下）

给定 $a_1,a_2,\dots,a_n$ 的初始值，试求有限的操作序列使 $a_1,a_2,\dots,a_n$ 变为同一个数。（模 $m$ 意义下）

解法

由加法交换律，操作的顺序并不影响结果。设 $P_1,P_2,\dots,P_k$ 分别进行了 $x_1,x_2,\dots,x_k$ 次，则 $a_1,a_2,\dots,a_n$ 变为 $a_1+x_1P_{11}+x_2P_{21}+\cdots+x_kP_{k1}$, $a_2+x_1P_{12}+x_2P_{22}+\cdots+x_kP_{k2}$, $\dots,a_n+x_1P_{1n}+x_2P_{2n}+\cdots+x_kP_{kn}$，即

$S'=S+PX$

其中 $S'=\begin{bmatrix} a_1' \\a_2' \\\vdots \\a_n' \end{bmatrix},$ $S=\begin{bmatrix} a_1 \\a_2 \\\vdots \\a_n \end{bmatrix},$ $X=\begin{bmatrix} x_1 \\x_2 \\\vdots \\x_n \end{bmatrix}$， 不妨将操作 $P_i$ 记为向量 $\begin{bmatrix} P_{i1} \\P_{i2} \\\vdots \\P_{in} \end{bmatrix}$ 则 $P=\begin{bmatrix}P_1&P_2&\cdots&P_k\end{bmatrix}$

变形得到

$PX=S'-S$

这是一个模 $m$ 意义下的线性方程组。我们只要给出一个解就解决了问题。

如果 $m$ 为质数，则除 $[0]$ 以外都有数论倒数。任取符合要求（即所有数相等）的 $S'$，使用高斯消元法即可解决问题。

$m$ 为质数的幂时，设 $m=p^t$，作高斯消元法，当进行到某一列时，若对角线元素无数论倒数（即有因子 $p$），则在下方将被消除的元素中找到与 $p$ 互质的元素，两者所在两行交换，便可正常进行消元。若所有将被消除 的元素中均是 $p$ 的倍数，则选取因子 $p$ 的次数最小的元素与原来的对角线元素所在两行对换，消元可正常进行。

$m$ 为一般合数时，分解为不同质数的幂相乘的形式，分别改写成模不同质数的幂的线性方程组的形式并解之，最后用中国剩余定理合并解即可。

$m$ 不为质数的情况任选 $S'$ 可能无解，因此需要枚举 $O(m)$ 个 $S'$ 来寻找解。若 $m$ 较大，计算上建议记录高斯消元法的步骤（表示为左乘原系数矩阵的矩阵）。

应用于原神解谜

原神中相关谜题之于上述模型是特例中的特例，虽然简单但也正是这些谜题引出了上述问题与思考。

如图谜题，即对其中某一方块，攻击之可改变自己和其余方块上的数字（以模$3$加法的形式），原神中应该都具体为自己和相邻方块数字+1。解密目标为通过一连串攻击操作使所有方块数字相同。

游戏内另有一类解密与此方块相同，但攻击是改变朝向，目标为所有方块朝向一致，与上述数字型解密内核相同。数字型是模 $3$，朝向型是模 $4$，即 $m=3$ 或 $4$。

对于有 $n$ 个方块的谜题，$n$ 个方块上现有的数字即为 $S$。$n$ 个方块正对应 $n$ 个操作，可按照操作的影响写出矩阵 $P$。解方程组得到答案。

以图中谜题为例， $P=\begin{bmatrix} 1&1&0&0&0 \\1&1&1&0&0 \\0&1&1&1&0 \\0&0&1&1&1 \\0&0&0&1&1 \end{bmatrix},$ $S=\begin{bmatrix} 1 \\1 \\2 \\1 \\1 \end{bmatrix}$ ，此处模数$3$为质数，故 $S'$ 可任取，这里取 $S'=\begin{bmatrix} 0 \\0 \\0 \\0 \\0 \end{bmatrix}$。

得到方程 $\begin{bmatrix} 1&1&0&0&0 \\1&1&1&0&0 \\0&1&1&1&0 \\0&0&1&1&1 \\0&0&0&1&1 \end{bmatrix} \begin{bmatrix} x_1 \\x_2 \\x_3 \\x_4 \\x_5 \end{bmatrix}\equiv \begin{bmatrix} 2 \\2 \\1 \\2 \\2 \end{bmatrix} \pmod 3$

给出一个解：$X=(2,0,0,1,1)^\mathrm{T}$，即攻击最左边的方块两次，最右边的两个方块分别一次即可。