矩阵哈希

矩阵哈希

矩阵哈希可以解决一系列消消乐问题，即：

​ 给定一个序列 \(A\) ，每次可以消除相邻相同两项，问是否可以消除完。

这一类问题。

做法

我们对每个字符 \(c\) 随机一个矩阵 \(M_c\)，那么当出现奇数次的时候乘 \(M_c\) ，出现偶数次的时候乘他的逆 \(M_c^{-1}\) 。那么当一个序列里的所有数按顺序乘起来为 \(I\) 的时候，此时这个序列就可以被消掉了。

这个看起来很傻卵，为啥不能用数呢？

容易发现矩阵和数的最大区别就是不具备交换律。

具体地例子是：

\(ABAB\) ，这个在矩阵的时候是 \(M_A\cdot M_B\cdot M_A^{-1}\cdot M_B^{-1}\)， 很显然乘起来并不是 \(I\) ，但是当他是数的时候就寄了。

这时候我们就知道矩阵的牛逼之处了：

由于不具备交换律，那么此时由于只具有结合律，这种类似括号匹配的事情就可以轻松处理。

更多的，我们可以设置 \(M_c=M_c^{-1}\)，这样就不用考虑奇偶了。

我们设 \(|M_c|=D\) ，那么

\({\begin{bmatrix}a,b\\c,d\end{bmatrix}}^{-1}=\begin{bmatrix}\frac{-d}{D},\frac{b}{D}\\\frac{c}{D},\frac{-a}{D}\end{bmatrix}\)

只要满足 \(D=1\)， \(a+d=0\) 即可。

随机出 \(a\) 和 \(b\) ，那么 \(d=-a\) ，\(c=\frac{ad-1}{b}\) 。

具体的，我们来看一些例题

CSP-S2023 T2：

​ 问有多少连续子串可以被消空。

那么从前往后计算前缀和，只要记录有多少个 \(sum_j=sum_i^{-1}\) 即可，这个直接扫一遍 map 存一下就行。

存 map 只要定义 \(<\) 和 \(=\) 即可。

模拟T4：

​ 求有多少种方案可以使得交换不同的两个字符使得最后可以被消除。

一种复杂度更劣的做法是考虑 cdq 分治：

那么枚举交换的是哪个字符，计算出左端点前面的值和到 mid的值，用 \(map\) 存一下，再考虑右端点就行。

这样复杂度是 \(O(n\log^2n)\) 。

另一种更优的方法是：

直接考虑从后往前扫，那么每次新加一个字符相当于对目前的 \(map\) 整体在右乘一个矩阵，用一个 tag 维护一下就行。插入新矩阵就先右乘一下逆即可。复杂度是 \(O(n\log n)\)。

Flower's Land

这个好像才是刚开始的出处？（是花花的题好像

​ 两种操作，一种是区间值域右移：\(a_i=(a_i+1)\mod 3\)，另一种是问区间是否可以被消除。

做法就考虑线段树，提前维护好线段树上每个区间右移时候的值，那么只要修改 tag 就行了。

询问是简单的。