I. 起因
之前打比赛多次担心写单哈希被卡，但 N 神之前说他高中打过的所有比赛，但凡是字符串的题写 unsigned long long 自然溢出从来没被卡过。我信以为真，认为现在已经没有人素质差到卡别人单模哈希。后来我打了一些 AtCoder 的比赛也写了很多 ull 自然溢出也没事。直到 这场CF N 神 B 题 ull 自然溢出被卡到裂开，以为思路错了，直到赛后才发现是单哈希被卡了。
鉴于以上惨痛的经历，我决定学习一下毒瘤的卡单模数哈希的方法，来警示自己以及与
N
神心态类似的人：不要管出题人卡不卡，反正写双哈希就对了。（警钟撅烂（逃
II. 模 \(10^9\) 级别的大质数哈希
其实单模 \(10^9\) 级别的大质数哈希非常好卡，我们只需要随机一个长度为 \(10^5\) 级别的只包含小写字母的字符串 \(s\)，再任取一个大小为 \(100\) 左右的子串长度 \(k\)，那么 \(s\) 的所有长度为 \(k\) 的子串中大概率会存在哈希冲突的字符串。
那么概率到底有多大呢，我们可以使用生日悖论的方法来计算。
字符串 \(s\) 的长度为 \(k\) 的子串总共有 \(26^{k}\) 种可能，当 \(k = 100\) 时 \(s\) 的任意两个长度为 \(k\) 的子串几乎不可能相等，所以我们按照长度为 \(k\) 的子串均不同来考虑。（其实计算这个本身也是生日悖论）
因为 \(s\) 中总共有 \(10^5 - k + 1\) 个长度为 \(k\) 的子串，设 \(p\) 为模数，则第 \(1\) 个子串的哈希值不跟之前重复的概率为 \(\displaystyle{\frac{p}{p}}\)，第 \(2\) 个子串的哈希值不跟之前重复的概率为 \(\displaystyle{\frac{p - 1}{p}}\) ，第 \(n\) 个子串的哈希值不跟之前重复的概率为 \(\displaystyle{\frac{p - n + 1}{p}}\)。所以出现至少两个长度为 \(k\) 子串哈希冲突的概率为 \(\displaystyle{1 - \prod\limits_{i = 1}^{10^{5} - k + 1} \frac{p - i + 1}{p}}\)。当 \(p = 10^9 + 7, k = 100\) 时计算上式的值约为 \(0.9931958400\)。
根据以上结论，随便写个代码一随机就能找到两个哈希冲突的字符串，所以单模 \(10^9\) 级别的哈希千万不要写。
III. unsigned long long 自然溢出哈希
由于样本空间是 \(10^{18}\) 级别，非常大，直接采取生日悖论的方法难以卡掉。
其实我们用上面的方法算一下概率，取 \(p = 10^{18}\)，\(|s| = 10^{6}\)，\(k = 100\)，哈希冲突的概率约为 \(0.0000004999\)。（这其实也为两个 \(10^{9}\) 级别大质数的双模哈希的正确性提供了证明。）
所以我们要换一套方法来卡，这里一般的方法为构造法。
1. 对于底数为偶数的情况
构造字符串 baaa...（后面有 \(64\) 个 a）与
caaa...（后面有 \(64\) 个
a）即可卡掉。
这两个字符串的后 \(64\) 个字符均为
a，所以只需要关心第 \(1\)
个位置对哈希值的贡献。
对于第一个字符串，第 \(1\) 个位置对哈希值的贡献为 \(H(\text{"b"}) \times Base^{64} \bmod 2^{64}\)。
对于第二个字符串，第 \(1\) 个位置对哈希值的贡献为 \(H(\text{"a"}) \times Base^{64} \bmod 2^{64}\)。
因为 \(Base\) 为偶数，所以 \(Base\) 中至少含有一个因子 \(2\)，所以 \(2^{64} \mid Base^{64}\)，所以两个字符串的第 \(1\) 个位置对哈希值的贡献均为 \(0\)，所以两字符串哈希冲突。
2. 对于底数为奇数的情况
考虑进行如下构造：
- 定义 \(S_1 = \text{"a"}\)
- 令 \(\text{len}(S_i)\) 表示字符串 \(S_i\) 的长度
- 令 \(\text{not}(T)\) 为将字符串 \(T\) 中字符 \(\text{"a"}\) 变为字符 \(\text{"b"}\)，字符 \(\text{"b"}\) 变为字符 \(\text{"a"}\) 的函数
- \(S_i = S_{i - 1} + \text{not}(S_{i - 1})\)
\[ 令 $f_i = H(S_i) - H(\text{not}(S_{i - 1}))$，上述两式相减，可得 \] f_{i} = f_{i - 1} (Base{2{i-1}} - 1) $$ 当 \(f_i \bmod 2^{64} = 0\) 时，我们即可构造出两个哈希冲突的字符串。
注意到 \(Base\) 为奇数，所以 \(Base^{2^{i - 1}} - 1\) 必定为偶数。所以 \(f_{64} \bmod 2^{64}\) 必定为 \(0\)，但是这要构造出两个长度为 \(2^{63}\) 的字符串 \(S_{64}\) 和 \(\text{not}(S_{64})\)，理论上这两个串是哈希冲突的，但是因为长度太长，现实中显然无法进行读写。
注意到 \((Base^{2^{i - 1}} - 1) = (Base^{2^{i - 2}} + 1)(Base^{2^{i-2}} - 1) = (Base^{2^{i - 2}} + 1)(Base^{2^{i - 3}} + 1) \cdots (Base^{2^{1}} + 1)(Base^{2^{1}} - 1)\)。容易证明，上述的每一项都是偶数，所以 \(f_i\) 中至少含有 \((i - 1) + (i - 2) + \cdots + 1 = \displaystyle{\frac{(i - 1)i}{2}}\) 个因子 \(2\)。
由上述理论进行计算，\(f_{12}\) 中至少含有 \(66\) 个因子 \(2\)，所以 \(S_{12}\) 与 \(\text{not}(S_{12})\) 哈希冲突，长度仅为 \(2^{11}\)。
IV. 小结
至此，不管如何更换模数和进制，常见的单模哈希的所有情况均被上述算法卡掉。
所以一定要写双模！！！一定要写双模！！！一定要写双模！！！双模一定要改模数，不要只改进制！！！