题解：P12197 Hash Killer I

· · 题解

蒟蒻的哈希太蒻了，来这里练一下，发现其实练的是数学与构造 QAQ。

希望你看完之后也能自己想出来这个解法。可能废话有点多（试图详细一点的后果），大佬轻喷。

目标是构造冲突，我们希望能构造一对串 s, \bar s 使得模 2^{64} 意义下：

hash(s) \equiv hash(\bar s) \iff \Delta hash(s, \bar s) \equiv 0

显然，ans = s + \bar s。

朴素的想法，是使哈希值都为 k\cdot 2^{64}，由于模数只含有因子 2，当 base 是偶数的时候，l \geq 65 就可以产生冲突。

然而奇数 base 与 2^{64} 互素，考虑构造 \Delta，这与处理偶数并不冲突，只要长度够长即可保证偶数情况正确。

大方向是构造一组共轭字符串满足 \Delta hash_i = a_i 且不断生成更多因数 2，考虑构造较为简单的递推式，形式如下：

\forall \ i \geq 1,\ b_i = 2k,\ a_i = a_{i - 1} \cdot b_{i - 1}

这样当 l 大到 a_l = 2^{64} \cdot x 时即可，现在问题来到怎么构造这一对共轭的字符串 s_i, \bar s _i。

由于 a = \Delta hash 是递推生成的，考虑 hash 递推化，如果添加一对字符 c, \bar c：

\begin{aligned} s_i = c + s_{i - 1} \Rightarrow &hash(s_i) = hash(s_{i - 1}) + c \cdot base ^ {i - 1} \\ \bar s_i = \bar c + \bar s_{i - 1} \Rightarrow &hash(\bar s_i) = hash(\bar s_{i - 1}) + \bar c \cdot base ^ {i - 1} \\ \iff &\Delta hash_i = \Delta hash_{i - 1} + base^{i - 1} \cdot (c - \bar c) \\ \iff &a_i = a_{i - 1} + (c - \bar c)\cdot base ^{i - 1} \end{aligned}

这个形式不是我们想看到的。不过发现右边式子中含 base，a_{i - 1} 又调整了系数奇偶性，暗藏玄只因啊！。

先回头看怎么使 (c - \bar c)\cdot base ^{i - 1} = k \cdot a_{i - 1}。此时一对字符不够用了，应该是一对字符串 t, \bar t 满足：

hash(t) - hash(\bar t) = k \cdot a_{i = 1} \iff \Delta hash(t) = k \cdot \Delta hash(i)

等等，要不再看一眼？两个字符串的哈希值之差是另外两个已知字符串哈希值之差的倍数，相等不就完了吗！

所以令 t = s_{i - 1}, \bar t = \bar s_{i - 1} 即可，相当于是每次把自己拼在自己前面。

此时 a_i = a_{i - 1} \cdot (1 + base ^ {2^{i - 1}})，注意倍增字符串导致 base 的幂次发生了改变，不过这并不影响在 base 是奇数的时 1 + base ^ {2^{i - 1}} 仍为偶数。

回顾一下，生成的过程就是让一对共轭字符串进行倍增，每倍增一次就多一个因子 2 出来，最后生成足够多 2 后把两个字符串拼在一起输出，得到的就是答案串。其中倍增多因子 2 的操作是通过 \Delta hash 的递推关系构造出来的，正确性来自这个解法专攻 base 是奇数的情况，所以总是生成一个偶数 1 + base^{2^{i - 1}}。

对……对吗？不难发现长度坠机了。因为长度随因子 2 的数量指数级的增加，此时 l = 2^{65}，怎么办？

除了相等（k = 1），其实 t, \bar t 的构造还有一种，现在 k = -1，即 t = \bar s_{i - 1}, \bar t = s_{i - 1}，有系数仍为偶数：

a_i = (1 - base^{2^{i - 1}}) \cdot a_{i - 1}

问题在于 1 + base^{2^{x}} 每次只能生成一个 2。相反，base^{2^{x}} - 1 就能累积其因子个数：

1 - base^{2^{x}} = (1 - base^{2^{x - 1}}) \cdot (1 + base^{2^{x - 1}})

所以对于 1 - base^{2^{x}}，其包含的因子 2 的数量呈等差数列前缀和的形式，即 cnt(x) = \frac{x \cdot (x + 1)}{2} 个。浅算一下，x = 11, cnt(x) = 66，所以 l = 2^{11} 就已经完全足够了。

为了方便，令 s_0 = 0, \bar s_0 = 1，这样的好处是，交换前插的操作相当于是取反并放在自己前面。取反前置的操作实现更加精妙，难以论说，请读者根据代码自行理解：

#include<bits/stdc++.h>
using namespace std;
int main() {
    cout << (1 << 12) << ' ' << (1 << 11) << '\n';
    for (int i = 1; i <= (1 << 12); ++i)
        putchar('a' + (__builtin_popcount(i) & 1));
    return 0;
}