P14185 回文子串划分计数 题解

前置知识：回文自动机 PAM。

一些定义：

回文串：定义一个长度为 $n$ 的串 $S$ 是回文的，当且仅当 $\forall i\in[1,n],S_i=S_{n-i+1}$。

Border：一个长度为 $m$ 的串 $T$ 是长度为 $n$ 的串 $S$ 的 Border，当且仅当 $S_{[1:m]}=S_{[n-m+1:n]}=T$。

最长 Border：对于长度为 $n$ 的串 $S$，其最长 Border 定义为最大的正整数 $x<n$ 使得存在一个长度为 $x$ 的串 $T$ 是串 $S$ 的 Border。

周期：$m$ 是一个长度为 $n$ 的串 $S$ 的周期，当且仅当 $n\ge m$ 且 $\forall i\in[1,n-m+1],S_i=S_{i+m}$。

最小正周期：即最小的正整数 $m$ 使得 $m$ 是串 $S$ 的一个周期。

然后是一些引理（比较重要的已被加粗）：

• 对于一个长度为 $n$ 的串 $S$，若 $S$ 是回文串，则若长度为 $m$ 的串 $T$ 是 $S$ 的后缀，$T$ 必然是 $S$ 的一个 Border。
• 对于一个长度为 $n$ 的串 $S$，若长度为 $m$ 的串 $T$ 是 $S$ 的 Border，则 $|S|-m$ 必然是 $S$ 的一个周期。
• 若有长度为 $n$ 的串 $S$ 和长度为 $m$ 的串 $T$，满足 $n\le m\le 2n$，则 $S$ 串在 $T$ 串上的所有匹配位置下标构成等差数列。
• 在上一条的基础上，若该等差数列的长度 $\ge 3$，设其公差为 $d$，则有串 $S$ 的最小正周期为 $d$。
• 对于一个长度为 $n$ 的串 $S$，其所有长度不小于 $\frac n2$ 的 Border 的不同长度构成一个等差数列。

考虑扩展 Border 的定义，原有的 Border 可以看作是串 $S$ 在和自己匹配。于是可以类比 Border，定义 $\text{Border}^+(S)$ 是长度为 $n$ 的串 $S$ 长度不小于 $\frac n2$ 的 Border 长度组成的集合。更形式化的说：

根据上面的定义，可知对于任意长度为 $n$ 的串 $S$，均有 $\text{Border}^+(S)$ 是一个等差数列。

然后容易得到关键结论：

• 一个长度为 $n$ 的字符串 $S$，Border 可以划分为不超过 $O(\log n)$ 个等差数列。

证明的话就是考虑倍增的去划 $\text{Border}^+$，根据前面被加粗的第三条引理可知倍增划分后每一段都形如一个等差数列。而倍增的性质就是划分为 $O(\log n)$ 的部分处理，因此上述关键结论得证。

然后考虑类比 PAM 上的 fail 指针，额外再维护 slink 指针。记回文树上点 $x$ 的等差值 $\text{diff}(x)=\text{len}(x)-\text{len}(\text{fail}(x))$，则 $\text{slink}(x)$ 对应的点为 fail 指针形成的 fail 树上，距离 $x$ 点最近的祖先结点 $y$ 满足 $\text{diff}(x)\neq\text{diff}(y)$。根据上面的结论，可以知道对于回文树上任意一个结点 $x$，都有从 $x$ 开始跳 slink 指针直到到达根结点为止，最多只会跳 $O(\log n)$ 次。

现在回到最初的问题。先考虑一个朴素的 dp 解法：

设 $f_i$ 表示 $S_{[1:i]}$ 这个前缀划分为若干回文子段的方案数，那么考虑枚举 $i$ 所在回文子串的开始位置 $j$，有转移：

• $f_i=\sum\limits_{1\le j\le i}[s_{j:i}\text{ is a palindrome string}]f_{j-1}$

初始条件为 $f_0=1$。

直接暴力转移时间复杂度为 $O(n^3)$，用哈希等手段快速判断区间是否为回文串，时间复杂度可优化到 $O(n^2)$。

考虑到问题和回文串有关，因此想到 PAM。考虑一边建 PAM 一边利用 PAM 的性质和 fail，slink 指针快速维护出 $f$ 数组的值。考虑到前面提到的性质，回文串的回文后缀一定是该回文串的 Border，所以考虑从 $f_{i-\text{len}(\text{slink}(i))-\text{diff}(i)}$ 转移到 $f_i$。而每次在 PAM 中插入字符 $c$ 时，都从 PAM 中 $c$ 字符对应的结点 $x$ 开始向根跳 slink 指针，根据前面提到的性质，slink 指针跳到根结点的期望不超过 $O(\log n)$ 次，因此直接暴力模拟上述过程转移，时间复杂度为 $O(n\log n)$。

下面给出 P14185 的代码实现：

#include <stdio.h>
#include <string.h>
#define N 1000010
#define mod 998244353

char s[N], t[N];
int idx, la;
typedef struct
{
    int ne[26], cnt, len, fail;
    int diff, slink;
} Node;
Node tree[N];
int f[N], g[N];

void init();
int getfail(int, int);
void ins(char, int);
long long max(long long, long long);

int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    init();
    f[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        ins(s[i], i);
        for (int j = la; j > 1; j = tree[j].slink)
        {
            g[j] = f[i - tree[tree[j].slink].len - tree[j].diff];
            if (tree[j].diff == tree[tree[j].fail].diff)
                g[j] = (g[j] + g[tree[j].fail]) % mod;
            f[i] = (f[i] + g[j]) % mod;
        }
    }
    printf("%d\n", f[n]);
    return 0;
}

long long max(long long a, long long b)
{
    return a > b ? a : b;
}

void init()
{
    idx = 1, la = 0, tree[1].len = -1, tree[0].fail = 1;
}

int getfail(int x, int i)
{
    while (s[i] != s[i - tree[x].len - 1])
        x = tree[x].fail;
    return x;
}

void ins(char o, int i)
{
    int x = getfail(la, i);
    if (!tree[x].ne[o - 'a'])
    {
        tree[++idx].len = tree[x].len + 2;
        tree[idx].fail = tree[getfail(tree[x].fail, i)].ne[o - 'a'];
        tree[x].ne[o - 'a'] = idx;
        tree[idx].diff = tree[idx].len - tree[tree[idx].fail].len;
        if (tree[idx].diff == tree[tree[idx].fail].diff)
            tree[idx].slink = tree[tree[idx].fail].slink;
        else
            tree[idx].slink = tree[idx].fail;
    }
    ++tree[la = tree[x].ne[o - 'a']].cnt;
}

加强版（几乎是双倍经验）：CF932G Palindrome Partition。