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

· · 题解

Genetics

基因工程

翻译自 BalticOI 2018 Day 2 题解

感谢 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}) 的时间复杂度内完成计算，虽然实现起来有些麻烦，并且常数巨大。