题解

思路

原条件可以从两端向中间理解：每次选一个长度 $w$，要求当前剩余串的长度为 $w$ 的前缀与后缀完全相同，然后同时删去它们。每次删除对应最终分割中的一对子串。

做法

子任务 1：直接比较

设 $d_i$ 表示已经从左右两端各删去 $i$ 个字符的方案数。枚举下一对的长度 $w$，直接逐字符比较

$$s[i\ldots i+w-1]=s[n-i-w\ldots n-i-1].$$

相等时令 $d_{i+w}\mathrel{+}=d_i$。复杂度为 $O(n^3)$。

子任务 2：转化为偶回文分割

构造新串

$$t=s_0s_{n-1}s_1s_{n-2}\cdots s_{n/2-1}s_{n/2}.$$

考虑从两端各取长度 $w$ 的两个块。它们相等，当且仅当 $t$ 中对应的长度 $2w$ 的连续段是回文串。因此原问题等价于：把 $t$ 分割成若干偶数长度的回文串。

设 $f_i$ 表示 $t$ 的前 $i$ 个字符的方案数。枚举所有回文区间 $t[l\ldots r]$，当 $l$ 和 $r+1$ 都是偶数时执行

$$f_{r+1}\mathrel{+}=f_l.$$

用区间动态规划判断回文性，复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$。

子任务 3：回文树与等差链

扫描 $t$ 并建立回文树。每个节点表示一种回文串，失配指针指向它的最长真回文后缀。对节点 $v$ 定义

$$\mathrm{diff}_v=\mathrm{len}_v-\mathrm{len}_{\mathrm{link}_v}.$$

若 $v$ 与失配节点的 diff 相同，则它们属于同一条长度等差链；否则开启一条新链。seriesLink 直接跳到上一条链，所以每个位置只需枚举等差链，而不用枚举全部回文后缀。

对当前前缀长度 $i$，维护一条链对 $f$ 的贡献 aux：

$$\mathrm{aux}_v=f_{i-(\mathrm{len}_{\mathrm{seriesLink}_v}+\mathrm{diff}_v)} +[\mathrm{diff}_v=\mathrm{diff}_{\mathrm{link}_v}]\,\mathrm{aux}_{\mathrm{link}_v}.$$

只有 $i$ 为偶数时才把这些贡献加入 $f_i$，但奇数位置仍需刷新 aux，供下一位置的同差链使用。初值为 $f_0=1$，答案为 $f_n$。

该等差链优化的总复杂度为 $O(n\log n)$，实际回文树构建和链跳转在线完成；空间复杂度为 $O(26n)$。

复杂度

三个层级分别为 $O(n^3)$、$O(n^2)$ 和 $O(n\log n)$；满分算法空间复杂度为 $O(26n)$。

正确性

构造串中任意偶数长度回文段的第 $2j$ 个字符来自左侧块，第 $2w-1-2j$ 个字符来自右侧块中同一相对位置，所以回文条件与两块相等完全等价。每次选块对与每个偶回文段一一对应，故两种分割方案双射。回文树枚举当前所有回文后缀，等差链只合并相同 diff 的连续后缀，不改变贡献之和，因此动态规划恰好计数全部合法分割。