题解：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$ 可以简化，得到：

次数 $2^k$，一共有 $k+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$ 两个更大的数，甚至是两个未知的正整数，还能构造吗？