CF1913F Palindromic Problem 题解

· · 题解

不需要脑子的题目。但是没开 long long 把我送走了。

key observation（这也算 observation？）：改变一个字符后，所有经过它的，不以它为中心的回文串都消失了。

先枚举回文中心 x，求出原本的回文串数量 pans。

这里不妨先假设 x 是某个字符。x 是两个字符中间的情况是是类似的。

定义回文半径 r 为以 x 为中心的回文串的数量，考虑要使得一个回文中心的回文半径 r 增大，需要修改 s[x-r] 或 s[x+r] 为两者中的另一个。修改完之后，我们再求出 s[x+r+1\sim n] 和倒过来看的 s[1\sim x-r-1] 的最长公共前缀长度 len，则修改对答案的增加量是 len+1。

定义 f_{i,j} 表示将 s[i] 修改为字母 j 对答案增加的贡献（只考虑增加，不考虑减少）。这个用上述方法求即可。

另外还要考虑减少的回文串。对于一个固定的 x，若修改 s[j],x-r+1\leq j \leq x-1，以 x 为中心的回文串数量减少 r-i+j。当 x+1\leq j \leq x+r-1，减少量为 r+i-j。这两个量都可以表示为关于 j 的一次函数，对一次项系数和零次项系数分别差分维护即可。

由此我们可以快速求出将 s[i] 修改为 j 对答案的改变量。之后只剩下一些 trivial 的讨论，相信来补这道题的同学们应该能自己讨论明白。

因为是 CF 比赛，强烈不建议用哈希，这题用后缀数组求 \text{lcp} 应该是效率最高的。复杂度是 \Theta(n\log n+n|\sum|)，|\sum| 是字符集大小。

for reference only.