P9753 [CSP-S 2023] 消消乐 题解

这里是被说烂了的随机化线性做法。

相信大家都已经做过 QOJ 6504，因此我们考虑采用类似的办法通过此题。我们对每个字符随机一个 \(k\times k\) 的矩阵，并求出其矩阵的逆。

然后，我们在偶数位放原矩阵，在奇数位放逆矩阵，这样，一段区间合法当且仅当这段区间的矩阵积为单位矩阵 \(I\)，原因显然。我们对矩阵积做前缀和 \(s\)，就把条件转化为了，区间 \([l, r]\) 合法当且仅当 \(s_{l-1}=s_r\)，那么我们开一个什么桶记一下就好了。

时间复杂度取决于实现。比较好的实现是 \(k=2\)，快极啦！

据说不是所有满足结合律但不满足交换律的运算都能这么办。