频率也大概就是一天两题的样子，因为我还要做到一周 VP 两场 CF Div2。
这对于一个暑假才开始复健，一年没训的人来说已经很困难了/fn/ll
P9753 [CSP-S 2023] 消消乐
Description
给你一个字符串 \(s\)，让你求出 \(s\) 的偶回文子串个数。
\(|s|\le 2\times 10^6\)
Solution
做过类似的 trick，所以秒掉了。（怎么过了两年了我还是没改这题？？？）
首先是 35pts，很简单的括号序列匹配（洛谷上是红来着）
然后是 50pts，我们枚举 \(s\) 的所有偶子串的一半，然后和另一半进行比较，如果一样就说明是偶回文子串。哈希记录即可。
最后是 100pts。考虑对每一位字符赋随机矩阵，奇数位放矩阵 \(T\)，偶数位放 \(T^{-1}\)，最后哈希处理一下，如果一个子串每一位的矩阵相乘等于单位矩阵 \(I\) 就是答案。
复杂度近似线性。
qoj6504 Flower's Land 2
Description
给你一个由 \(012\) 组成的字符串 \(s\)，支持区间加 \(1\) 模 \(3\)（如 012 执行一次操作会变为 120）和查询是否是偶回文串。
\(|s|,q\le 5\times 10^5\)
Solution
和上面那个问题基本类似，所以秒掉了。
由于存在 \(012\) 三种，所以赋值成三种随机矩阵 \(T_1\)，\(T_2\) 和 \(T_3\)。奇数位放 \(T\)，偶数位放 \(T^{-1}\)。最后如果满足条件的话下面这个式子是成立的。
\[\prod_{i=l}^{r} T_i = I
\]
至于区间加，使用线段树维护即可。
时间复杂度是 \(O(n\log n)\) 乘上矩阵乘法复杂度。