题解 P4795 【[BalticOI 2018]基因工程】

### Genetics ### 基因工程 **翻译自 [BalticOI 2018 Day 2 题解](https://boi2018.progolymp.se/spoiler-day2.pdf)** **感谢 rqy 与 zzq 等 dalao 的大力帮助，才能有下面比较通顺的翻译。** 这个问题有一个简单的三次方复杂度做法，还有一个优美的基于随机化的二次方解法（原文： ``probabilistic quadratic solution``）。我们将在稍后描述这个算法。 我们先从二进制字符集的情况开始。这种情况下，我们可以让数学更优美一些：我们把两个字母 ``A`` 和 ``C`` 看作数字 $1$ 和 $-1$。「计算两个字符串 $a$ 和 $b$ 之间的不同程度」这个问题与「给一个矩阵 $A$ 的两行做点值乘法」同构，即对于 $j=1\ldots M$，计算 $A_{i,\,j}\cdot A_{i',\,j}$ 的和（为了降低常数 — 我们令和式等于 $K'=M-2K$ 而不是 $K$）。 > （译者：如果不能理解括号里的内容，请参考下面的原文。） > > (up to some constant factor and linear rescaling — instead of wanting sums to equal $K$, we want them to equal $K' = M = 2K$) 现在我们想要做的是检查对于所有满足 $b=a_{i'\neq i}$ 的行的点乘值是否为 $K'$。我们不需要针对所有的 $b$ 逐一进行计算，而是立即与其它行对比这个和的值。这有几种不同的实现，一个优美的方法是，为每一行选择一个随机的值 $w_i$，然后检查 $A\cdot(\sum_{i'}w_{i'}A_{i'})$ 与 $(\sum_{i'}w_{i'}-w_i)\cdot K'$ 是否相等（其中 $i$ 是我们正在检查的一行）。 > （译者：如果不能理解「检查 Foo 与 Bar 是否相等」，请参考下面的原文。） > > ... and then check that the dot product against the combined sum $\sum_{i'}w_{i'}A_{i'}$ equals $(\sum_{i'}w_{i'}-w_i)\cdot K'$ (where $i$ is the row we're checking). 用稍微具象一点的数学术语来讲，并且推广到更大的字符集，我们在每一行中随机选取 $w_i$，然后对于每一列 $j$ 中的字母 $c\in\{A,\,C,\,G,\,T\}$，令 $D_c$ 表示第 $j$ 列中每行字母为 $c$ 的 $w_i$ 之和。接下来我们可以通过计算和式 $\sum_j\sum_{d\neq A_{i,\,j}}D_d$ 来依次比较第 $a_i$ 行与其它各行。如果这一行是答案，因为这一行与如第 $A_{i'}$ 行的其它各行恰好有 $K$ 个字符不同，所以这个式子就等于其它各行 $w_{i'}$ 的和式的 $K$ 倍。 如果这一行不是答案，和式很有可能不等于那个值。将一行中的任何一个 $w$ 修改为不同的值都会改变和式的值，如果我们将答案对 $2^{64}$ 取模，则出错的概率约为 $2^{-50}$。因此这个算法将以非常接近 100% 的概率通过测试。 有趣的一些东西： 1. 要生成这题的测试数据非常麻烦。针对应该被卡掉的暴力，我们希望**几乎所有** 的行之间都有不为 $K$ 个的字符不同，但是要有一行恰好与所有其它各行有恰好 $K$ 个字符不同。出题人知道的唯一的恰好有相同个数元素不相同的矩阵有：单位矩阵 （其中 $N=M,\,K=2$）、常数矩阵（其中 $K=0$） 和广义 Hadmard 矩阵（其中 $N=M,\, K=N(1-1/A)$），以及它们三者的结合。其中 $A$ 表示 $|\Sigma|$。对于二进制字符集，Hadmard 矩阵被定义为一个大小为 $N\times M(N=M)$ 的 $0-1$ 矩阵，其中所有各行恰有 $N/2$ 个元素不同。对这种矩阵的研究已经十分深入，并且构造这个矩阵的一种简单的方法是递归：从矩阵 $$H=[1]$$ 开始，重复地用 $$\begin{bmatrix}H&H\\H&H\oplus1\\\end{bmatrix}$$ 替换掉 $H$。其中 $H\oplus1$ 表示 $H$ 的所有元素都异或 $1$。这会产生一个大小为 $2$ 的整数次幂的 Hadamard 矩阵。 对于 $|\Sigma| = 4$ 我们可以做一些更复杂的工作，将 $H$ 用 $$\begin{bmatrix}H&H&H&H\\H&H\oplus1&H\oplus2&H\oplus3\\H&H\oplus2&H\oplus3&H\oplus1\\H&H\oplus3&H\oplus1&H\oplus2\\\end{bmatrix}$$ 替代。 对这个矩阵会产生正确的矩阵的证明留给读者作为练习（这个构造来自 $GF(4)$ 的乘法表，要求有较高的数学素养）。 给定一个行与行之间都有 $K$ 个字符不同的矩阵，我们可以采用多种方式对矩阵进行一些扰动，以使答案唯一，例如复制矩阵的某些行或改变矩阵的一些二进制位。 这些复杂的构造过程部分解释了限制部分 — 难以构造字符集大小不为 $2$ 的整数次幂的 Hadmard 矩阵。 2. 存在一个复杂度低于 $O(n^3)$ 的解法：由于矩阵元素的取值集合为 $\{-1,\,1\}$，我们可以简单地计算 $A\cdot A^T$，然后从中寻找值为 $K$ 的元素，矩阵乘法在理论上可以在 $O(n^{2.373})$ 的时间复杂度内完成计算，虽然实现起来有些麻烦，并且常数巨大。