本题的题解中提到了这样一种哈希方法：

还有一种方法是把哈希值设成矩阵的形式，例如每个字符都对应一个 $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