回文划分题解

思路

对一个美丽串从左端开始，每次取最短的偶回文前缀。这个贪心过程得到的划分是唯一的最大段数划分。因此，对每个起点 $i$，只要找到从 $i$ 开始的最短偶回文串，其右端之后还能接出的美丽串数量就已经求出。

设 next[i] 为从 $i$ 开始的最短偶回文串结束后的第一个位置。若不存在这样的偶回文串，则从 $i$ 开始不存在美丽子串；否则从 $i$ 开始的美丽子串数量等于从 next[i] 开始的数量再加一。

关键转化是用偶回文半径快速求所有 next[i]。

做法

先用 Manacher 算法求每个偶回文中心 $c$ 的最大半径 $d_c$。该回文覆盖半开区间 $[c-d_c,c+d_c)$。对于起点 $i$，中心 $c>i$ 能产生一个从 $i$ 开始的偶回文串，当且仅当

而最短的回文对应最小的可行中心 $c$。建立一棵维护区间最小值的线段树，叶子 $c$ 保存 $c-d_c$。查询后缀区间 $[i+1,n)$ 中第一个值不大于 $i$ 的位置，即可得到最小中心，并令

从右到左计算 $dp_i$。若 next[i] 不存在，则 $dp_i=0$；否则

答案为所有 $dp_i$ 之和。

第一档可以直接比较每个偶长度子串是否为回文。第二档先用平方级动态规划预处理所有偶回文区间，再为每个起点寻找最短者。

正确性证明

设某个美丽串存在一种偶回文划分，其第一段结束于 $r$；再设从左端开始的最短偶回文前缀结束于 $l$。若 $2l\le r$，两个回文的对称关系能把第一段进一步拆成以最短前缀开头的若干偶回文；若 $2l>r$，两个回文的重叠部分会推出一个比 $l$ 更短的偶回文前缀，与 $l$ 的最小性矛盾。因此任意美丽串都可以先取最短偶回文前缀，且最大段数划分由这一选择唯一确定。

对于起点 $i$，线段树返回的最小中心 $c$ 满足 $c-d_c\le i$，所以区间 $[i,2c-i)$ 是偶回文串；任何更短的偶回文必须拥有更小中心，但查询保证不存在这样的中心。因此 next[i] 正是贪心选择的结束位置。

由贪心引理，从 $i$ 开始的每个美丽子串要么恰好是这一最短偶回文，要么在它后面继续接一个从 next[i] 开始的美丽串，二者一一对应，所以转移 $dp_i=dp_{next[i]}+1$ 正确。求和便得到全部美丽子串数量。

复杂度

每个测试用例中，Manacher 算法为 $O(n)$，线段树查询总计 $O(n\log n)$；空间复杂度为 $O(n)$。所有测试用例的复杂度按长度总和计算。