问题重述

给定一个长度为偶数 $n$ 的字符串 $s$，求将其分割成若干子串 $p_1, p_2, \dots, p_k$（$k$ 为偶数）的方案数，使得子串序列是回文的，即：

$$p_i = p_{k-i+1}, \quad \forall 1 \le i \le k$$

答案对 $10^9+7$ 取模。

---

核心转化

1. 构造新字符串 $t$

设 $n = |s|$ 为偶数。定义新字符串 $t$ 如下：

$$t = s[0]\,s[n-1]\,s[1]\,s[n-2]\,s[2]\,s[n-3] \dots s[n/2-1]\,s[n/2] $$

即将 $s$ 的首尾交替取出，构成新串 $t$。

例如，$s = \text{"abcdcdab"}$，$n=8$：

• $s[0]=a$, $s[7]=b$, $s[1]=b$, $s[6]=c$, $s[2]=c$, $s[5]=d$, $s[3]=d$, $s[4]=c$
• 得到 $t = \text{"abbccddc"}$

2. 转化后的等价问题

定理：原问题中 $s$ 的合法分割与 $t$ 的偶数长度回文子串分割一一对应。

证明：

设原分割为 $p_1, p_2, \dots, p_k$（$k$ 为偶数），且满足 $p_i = p_{k-i+1}$。

考虑对称的一对 $p_i$ 和 $p_{k-i+1}$。设 $p_i = x_1 x_2 \dots x_m$（$m$ 为 $p_i$ 的长度），则 $p_{k-i+1} = x_1 x_2 \dots x_m$ 相同。

在 $t$ 中，这两个子串对应的部分为：

$$x_1 x_m x_2 x_{m-1} \dots x_{m-1} x_2 x_m x_1$$

这是一个长度为 $2m$ 的回文串（偶数长度）。

由于整个分割是对称的，$t$ 会被划分成若干个这样的偶数长度回文子串。

反之，给定 $t$ 的一个偶数长度回文子串划分，也可以还原出 $s$ 的一个合法分割。

因此，问题转化为：

求将字符串 $t$ 分割成若干个偶数长度回文子串的方案数。

---

动态规划设计

设 $dp[i]$ 表示前缀 $t[1..i]$ 的合法分割方案数（$i$ 从 $1$ 到 $n$，$n$ 为偶数）。

边界条件

$$dp[0] = 1$$

表示空串有一种分割方式。

转移方程

对于 $i \ge 1$，如果 $i$ 是奇数，则无法分成偶数长度回文子串（因为总长度是奇数，而每个子串长度是偶数），所以：

$$dp[i] = 0 \quad \text{若 } i \text{ 为奇数}$$

对于偶数 $i$，考虑最后一段子串 $t[j+1..i]$，它必须是偶数长度回文串。那么：

$$dp[i] = \sum_{\substack{j < i \\ i-j \text{ 为偶数} \\ t[j+1..i] \text{ 是回文}}} dp[j] $$

直接枚举所有 $j$ 的复杂度是 $O(n^2)$，不可行。我们需要快速找到所有使得 $t[j+1..i]$ 是回文串的 $j$。

---

快速求所有回文后缀

对于每个位置 $i$，我们需要知道所有以 $i$ 结尾的回文子串的起始位置。

方法一：回文自动机（Eertree）

回文自动机（Eertree）可以在 $O(n)$ 时间内构建，并维护每个位置的所有回文后缀。具体地：

• 每个节点代表一个回文串
• 通过后缀链接可以遍历所有以当前位置结尾的回文串

对于偶数长度回文串，我们只需要考虑长度为偶数的节点。

设 $pos[i]$ 表示以 $i$ 结尾的所有偶数长度回文串的起始位置集合，则：

$$dp[i] = \sum_{start \in pos[i]} dp[start-1]$$

通过 Eertree 可以在 $O(n)$ 内完成转移，总复杂度 $O(n)$。

---

方法二：Manacher + 差分优化（$O(n \log n)$）

另一种方法是利用 Manacher 算法求出每个位置的最长回文半径，然后通过差分数组快速更新 $dp$ 值。

设 $rad[i]$ 表示以 $i$ 为中心的最长回文半径（包括中心），则：

• 对于奇数长度回文中心 $i$，回文半径为 $rad[i]$，对应回文串长度为 $2 \cdot rad[i] - 1$（奇数），我们不需要
• 对于偶数长度回文中心 $i$ 和 $i+1$ 之间，回文半径为 $rad[i]$，对应回文串长度为 $2 \cdot rad[i]$（偶数）

对于每个偶数长度回文中心，设其覆盖的起始位置为 $j$，则对于所有满足 $start \in [j, j+rad[i]-1]$ 的位置，都可以从 $dp[start-1]$ 转移到 $dp[start+2 \cdot rad[i]-1]$。

这可以用差分数组在 $O(n)$ 内处理。

---

算法步骤（基于 Eertree）

1. 构造 $t$：根据 $s$ 交替取首尾字符得到 $t$，长度为 $n$。
2. 构建回文自动机：
   • 每个节点存储：长度 $len$，后缀链接 $link$，转移边 $next[c]$
   • 额外维护 $evenLink$ 指向最近的长度为偶数的回文后缀（或直接判断 $len$ 是否为偶数）
3. 动态规划：
   • 初始化 $dp[0] = 1$
   • 遍历 $i$ 从 $1$ 到 $n$：
     • 如果 $i$ 为奇数，$dp[i] = 0$
     • 否则，在回文自动机上沿着后缀链接遍历所有以 $i$ 结尾的回文串：
       • 若当前回文串长度为偶数，设其起始位置为 $start = i - len + 1$，则 $dp[i] \mathrel{+}= dp[start-1]$
4. 答案即为 $dp[n] \bmod (10^9+7)$

---

复杂度分析

• 构建 $t$：$O(n)$
• 构建回文自动机：$O(n)$
• 动态规划：每个字符最多访问 $O(\log n)$ 个后缀链接（均摊 $O(1)$），总复杂度 $O(n)$

因此总复杂度 $O(n)$，空间复杂度 $O(n)$。

---