Luogu分析先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。考虑第三类的最长长度怎么求。枚举中点 $i$,发现此时的扭动串变成了三段:一段是某个串中 $i$ 向外扩展出的回文串,一段是 $A$ 中继续向左扩展出的串,一段是 $...
BZOJ分析首先在每两个字符中插入 texttt{#},然后跑 Manacher。记 Manacher 求出的数组为 $f$。考虑每个询问。我们首先扩展到插入 texttt{#} 后的串,即令 $l\leftarrow 2\times l-1$,$r\leftarrow 2\times r+1$。设新串中的答案为 $ans'$,则原答案为 $\frac{ans'-(r-l+2)}{2}$,意...
LuoguBZOJ分析下文中默认字符串的下标从 $0$ 开始。可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。后面的就是 manacher 板子,考虑怎么求前面的。设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量,则有后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1$,累加起来即可...
LuoguLOJ分析这个“翻转”操作很容易想到回文。考虑一个位置怎样才是合法的。可以发现该位置一定满足以下两个条件之一:回文半径右侧达到 $|S|$ 。回文半径左侧达到 $1$ ,且右端点合法。那么只需要用 manacher 求出回文半径,然后从后往前判断就好了。代码// =================================== // author: M_sea // ...
LuoguBZOJ分析$\mathrm{manacher}$ 。处理出两个数组 $L[i]$ 和 $R[i]$ ,分别表示以 $i$ 为开头/结尾的最长回文串长度。显然可以在跑完 $\mathrm{manacher}$ 后 $O(n)$ 得出。然后直接扫一遍求出 $\max\{L[i]+R[i]\}$ 就行了。需要注意的是,这里的 $L[i]$ 和 $R[i]$ 都不能为 $0$ 否则你会在...
LuoguBZOJ分析$\mathrm{manacher}$ 。先求出以每个数为中心的回文串长度。因为只关心奇数长度的串,所以没必要补#。然后考虑怎么统计答案。设 $o[i]$ 表示长度为 $i$ 的回文串的个数。因为长度为 $i$ 的回文串包含了长度为 $j\;(j<i)$ 的回文串,所以可以先把每个长度加进去,再求一遍后缀和。算答案就很简单,直接扫一遍,然后用快速幂计算就行了。具体...
LuoguBZOJ分析把每条边的长度和每个角的大小按顺序排列,可以组成一个环。把这个环在某条对称轴的地方断开,形成的串显然是回文的。于是把这个环倍长,然后长度 $> len$ 的回文串个数就是答案(这里的 $len$ 是环长)。直接跑 $\mathrm{manacher}$ 即可。具体的,长度可以不开根号,角的大小可以用叉积。然后最后的答案要 $/2$ ,因为每条对称轴被算了两次。具...