本题的题解中提到了这样一种哈希方法:
还有一种方法是把哈希值设成矩阵的形式,例如每个字符都对应一个 $3 \times 3$ 的随机小矩阵。
这种做法至少看起来是很靠谱的,因为它不交换,也抵抗了 $ab + cd \neq ad + bc$ 这种攻击。但它到底有没有理论正确性呢……
好消息是,这个做法对于自由群的 hash 来说是正确的,也就是说,我们把每个字母看做一个有 $k\times k$ 个变量的矩阵,那么对于两个不同的字符串,它们对应的矩阵乘起来的结果是不同的。
这个可以使用 乒乓引理 证明。(这里具体证明先坑着,我之后有时间再补全)
所以我们只要随机带入一组值,Schwartz–Zippel 引理就保证了检验的正确率。
但遗憾的是,对于自由代数来说,这个 hash 却是不正确的,也就是说,我们有两个 $W_1 = \sum_i x_{i1}\cdots x_{i \ell_i}$ 和 $W_2 = \sum_j y_{j1}\cdots y_{j k_j}$,它们是一些串的数量和,其实 $W_1\neq W_2$,但我们任意选取一个给每个字符带入一个 $3\times 3$ 矩阵的方案,都使得 $W_1 = W_2$!
我不能直接在这里把这个构造写出来,因为它太长了,但实际上这是一个对于 $k\times k$ 的矩阵都能给出的构造,叫做 Amitsur–Levitzki 定理:
设(非交换)多项式 $$ S_n(x_1,\dots,x_n) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) x_{\sigma(1)}\cdots x_{\sigma(n)}, $$
那么任意 $2k$ 个 $k\times k$ 的交换环 $R$ 上的矩阵都满足 $S_{2k}(M_1,\dots,M_{2k}) = 0$。
(证明可以参看 李文威 代数学讲义 的 15.8 节。)
所以,我们令 $W_1$ 是那些偶置换对应的多项式,$W_2$ 是那些奇置换对应的多项式,我们就有 $W_1=W_2$,但任意带入 $k$ 阶矩阵都会得到 $W_1=W_2$ 了。
hack #13502 是根据 Amitsur–Levitzki 定理生成的一组 $k=2$ 时候的样例,看起来不止我一个人尝试过这种做法,所以重测之后 97 分的人数从 62 个变成了 80 个。
但是由于本题的数据范围的限制,$k=3$ 的时候粗暴地枚举这些串就不行了。欢迎大家继续尝试造 hack,把更大的 $k$ 的代码叉下来。
现在状态(可以提醒我更新):
- 2 阶矩阵 hacked by EntropyIncreaser hack #13502
- 3 阶矩阵 hacked by hos_lyric hack #13511
- 4 阶矩阵 hacked by hos_lyric hack #13512
- 5 阶矩阵 尚未被 hack