题解：P12197 Hash Killer I

· · 题解

被绿题·注意力高手吓晕。

这个问题是怎么推导出来的？

我先看看要做什么。

原来是出题人下来战书，要我构造两个串，只包含 [0,26) 内的整数，满足对于任意的 B，两个串的 hash 的结果都相等。

hash 计算方式是：一个串 a=a_0a_1 \dots a_{n-1} 的 hash 值 H_a(B)=\sum_{i=0}^{n-1} a_i B^i \pmod {2^{64}}。相当于把串视为 B 进制数 \pmod {2^{64}} 的结果。

我直接输出 a aa aaa，hash 值全是 0。没想到他预判了我的预判，要求必须串长相等，不讲武德。

他还真有勇气！我看了看 hash 的定义，原来是个多项式 \sum_{i=0}^{n-1} a_i B^i。我马上定义一个多项式 H_a(x)=\sum_{i=0}^{n-1} a_i x^i，那 H_a(B) \pmod {2^{64}} 就是 hash 值。

要构造两个串 a,b 对于任意 B 的 hash 都相等，其实就是要构造两个 \pmod {2^{64}} 相等的多项式 H_a(x) 和 H_b(x)，并且每一项系数都是[0,26) 内的整数。两者相等，也就是两者相减得到的多项式 D(x) \equiv 0\pmod {2^{64}}。D(x)=H_a(x)-H_b(x) 的系数可以取所有 (-26,26) 内的整数，把正系数和负系数分别分给 a,b 就行了。

所以任务是，构造一个整系数多项式 D(x)，在整数点取值永远是 2^{64} 的倍数，且系数在范围 (-26,26)。

我一看，马上构造出了 x^{64}(x+1)^{64}，因为 x,x+1 总有一个是偶数，它 64 次方肯定是 2^{64} 的倍数了。但是这个系数太大了。x^{64} 这一项是不影响系数范围的，需要想办法让 x 取奇数时的偶数项系数变小。

那我只要一直让次数增大不重复，系数不就变小了：(x+1)(x^2+1)(x^4+1)(x^8+1)\dots

这样系数是小了，但是序列长度有点太大了。

不过这是等比求和，多乘个 x-1 可以简化，得到：

\begin{aligned} x^{2^k}-1 & =(x^{2^{k-1}}+1)(x^{2^{k-1}}-1)\\ & =(x^{2^{k-1}}+1)(x^{2^{k-2}}+1)\dots (x+1)(x-1) \end{aligned}

次数 2^k，一共有 k+1 个偶数项。

就还可以这样挤一挤：

(x^{2^k}-1)(x^{2^{k-1}}-1)(x^{2^{k-2}}-1)\dots (x-1)

仍然只有 0,\pm 1 的系数，不过一共有 \sum_{i=1}^{k+1} i=\frac{k(k+1)}{2} 个偶数项。取 k=11 即可 \ge 64。

这样构造出了满足条件的 D(x)=x^{64}(x-1)(x^2-1)(x^4-1)\dots (x^{2^{11}}-1)。取 D(x) 中系数为 1,-1 的项分别作为两个串的 b 字符位置，其余均填 a，即可构造出串。串长是 2^{12}+64。

这个序列即为其它题解中提到的 Thue Morse 序列。

你学会了吗？

练习1. 上面我们只用了 ab 两个字符，或者说限制了 D(x) 的系数绝对值 \le 1。如果用满 a-z，你能不能构造出更短的串？

练习2. 如果不是对 2^{64} 而是对 3^{30} 或者 10^{15} 取模怎么构造呢？

bonus. 这个问题我们认为 ab 分别对应 01。如果 ab 分别对应 x_0,x_1 两个更大的数，甚至是两个未知的正整数，还能构造吗？