今天是个好日子啊，写一个哈希都被卡啊~~~
万恶之源：「CF580E」Kefa and Watch，一道抽象的卡哈希的哈希题。
但观察发现，无论我怎么修改我的基数(base)，我都无法通过 Text 75，于是便研究了一下，学到了如下的 Hack 方式：
- 对于 base 为偶数的：
- 只需要有连续一段相同的字符其长度大于 \(64\)，哈希值就会归零
- 对于 base 为奇数的：
- 对于一个只包含 \(a,b\) 的字符串 \(s\)，我们定义 \(\overline{s}\) 为将 \(s\) 中的 \(a\) 变为 \(b\)，\(b\) 变为 \(a\) 的串。
- 令 \(f_0=\texttt{"a"}\)，\(f_i=f_{i-1}+\overline{f_{i-1}}\)。再定义 \(\mathrm{Hash}(s)\) 表示为 \(s\) 的哈希值，则有 \(\mathrm{Hash}(f_{i})=\mathrm{Hash}(f_{i-1})\times \mathrm{base}^{2^{i-1}}+\mathrm{Hash}(\overline{f_{i-1}})\)，而 \(\mathrm{Hash}(\overline{f_{i}})\) 与前式对称，就不再赘述。
- 记 \(g_{i}=\mathrm{Hash}(f_i)-\mathrm{Hash}(\overline{f_i})\)，则有 \(g_{i}=g_{i-1}\times (\mathrm{base}^{2^{i-1}}-1)\)。
- 易证 \(2^{i}|\mathrm{base^{2^{i-1}}}-1\)，所以 \(2^{i\times (i+1)}|f_{i}\)，对于 \(i\geq 11\)，\(\mathrm{Hash}(f_{i})=\mathrm{Hash}(\overline{f_{i}})\)。
- 所以构造一个长度为 \(4096\) 的字符串即可。
参考文献：
对于上述易证的解释：（\(\LaTeX\) 公式太难打，就直接上手写）
