【做题记录】P9753 + CF1223F

· · 个人记录

一题多解，写一下。

Update：25.09.28 LCA 讲课后，补充了栈做法的正确性证明。

Sol.1 DP 优化

朴素地设 f_i 表示以 i 为结尾的合法子串数，则有 f_i=f_{g_i}+1，其中 g_i 表示 [g_i,i] 合法的最大下标。可以想到初始化 g_i=i，然后不断让 g_i=g_{g_i-1} 直到 a_{g_i}=a_i，但是这种做法最劣是 O(n^2) 的，会被卡。

所以考虑快速求出 g_i 这个位置，话说这里题解强得离谱导致我对着题解看了好久。考虑再设 to_i 表示 [to_i+1,i] 合法的最小下标，mx_{i,j} 表示 [i+1,mx_{i,j}] 合法且 a_{mx_{i,j}}=j 的最大下标。

初值 to_i=i，还是先找到 k=to_{i-1}，然后找到 x=mx_{k,s_i}，所以现在保证了 [k+1,x],[k+1,i-1] 均合法且 s_x=s_i，所以 [x+1,i-1] 合法，从而两端加上 s_x=s_i 后 [x,i] 仍然合法。此时转移 to_i=to_{x-1},f_x=f_{x-1}+1，然后维护 mx_{to_i,s_i}=i。

栈做法

判断区间是否合法只需要像括号序列一样用栈维护还没有匹配的字符，如果最终空了就合法。如果枚举所有区间再依次判断，复杂度为 O(n^3)。如果枚举左端点 l，从 l 开始每空一次便是一个合法区间，复杂度为 O(n^2)。

最终版本是维护整个区间的栈序列，只要 x,y 分别放进去后栈中元素相同，那么 [x+1,y] 就是一段合法区间。所以问题变成了判断栈序列相同，以下是复杂度正确的优化做法。

正确性证明：

区间合法显然是可加的，即 A,B 均合法一定有 AB 合法。另外显然操作顺序是任意的，即任意消除可消的元素都能消完合法区间，因此若 AB 合法且 A 合法则一定有 B 也合法。那么若前缀 S 和更长的前缀 T 消完的栈序列均为 R，将 R 倒过来接在前面，有 RS 和 RT 均合法，这两者相减即可得到该区间合法。同样该区间合法也能反推出 S 和 T 一定相同，因此该结论正确。

Sol.2 矩阵乘法（群论思想）+ 哈希

考虑如果能用运算消掉两个元素的话，就相当于群论中 aa^{-1}=e。所以每种元素第偶数个赋上 a，第奇数个赋上 a^{-1}。但问题是如果群中满足交换律，会把 aba^{-1}b^{-1} 这种串判定为合法，所以必须使用不满足交换律的群。

可以使用矩阵乘法群，手算构造出互逆矩阵并放到序列里。对整个序列做前缀乘法，判断相同矩阵的出现次数即可，需要用哈希判断。所以我感觉不如 Sol.3 直接哈希，复杂度时间 O(nx^3)，空间 O(nx^2)，其中 x 为矩阵大小。

Sol.3 栈 + 哈希

维护前 i 个时栈序列的哈希值 h_i，弹栈时就跳到栈顶的前一个位置的哈希值，否则就把新的值加入 h_{i-1}，开个 map 维护一下每个哈希值出现的次数就行了。

但是 10^9 级别模数很可能出现哈希冲突，需要用双模哈希或者用自然溢出扩大到 10^{18} 级别才能比较稳定地通过，但我用哈希冲突也试了俩数才全过。

复杂度：时间 O(n\log n)，空间 O(n)。

Sol.4 栈 + Trie

用 Trie 维护每次出现的栈序列，发现每次栈序列只会变化 1，也就是要么删一个数，要么加一个数，对应到 Trie 上也就是向父亲或儿子跳一下。每次都给对应的节点计数即可，最终答案即为 \sum\frac{k(k-1)}2，k 是每个节点对应的栈序列出现次数。

复杂度上由于一共只会修改 n 次，Trie 中至多有 n 个节点。如果用数组存子节点则时间 O(n)，空间 O(nS)，用 map 的话时间 O(n\log n)，空间 O(n)。后者可以无视值域，而且其实时间常数也比较小。