题目概述

CF932G

解题报告

首先原题意有点恐怖，我们需要进行一定的转化。原题意需要分成偶数个串，然后前后对称相同，如果我们把串的后一半翻转，那么就会发现前后对应的两个字符串是互相翻转的。

进一步转化，如果 $A$ 和 $B$ 互相翻转，那么穿插接起来显然是一个偶数长度的回文串，如：$ab|cd|cd|ab$ 后面翻转后为 $ab|cd|ba|dc$ ，就变成了 $ab$ 和 $ba$ ，$cd$ 和 $dc$ 对应，穿插起来之后就是 $abba,cddc$ 即两个回文串。

因此原题意转化为，把字符串后一半翻转，穿插进前一半，然后求多少种方案把新字符串分成偶数长度的回文串。

定义 $f_i$ 表示 $[1,i]$ 分成回文串的方案数，不难想到枚举以 $i$ 结尾的回文串进行转移，可以利用PAM：

$$ f_i=\sum\{f_j|S[j+1,i]\text{ is Palindrome}\} $$

但是这显然是 $O(n^2)$ 的，无法接受，因此我们需要用到一个PAM科技Palindrome Series。

推荐博客：Border Series在回文自动机上的运用，字符串科技：Palindrome Series，A bit more about palindromes。

这里就介绍和解释几个关键结论：

1. 一个串的长度在 $[2^k,2^{k+1})$ 范围内的Border长度构成等差数列（Border Series）。

2. 字符串 $T$ 是回文串 $S$ 的一个回文后缀，当且仅当 $T$ 是 $S$ 的Border。

   回文后缀一定也是回文前缀，因此满足Border性质。

3. 字符串 $S$ 存在回文Border $T$ ，且 $|T|\ge{|S|\over 2}$ ，则 $S$ 是回文串。

   即 $S$ 前 $|T|$ 个字符构成回文，后 $|T|$ 个字符也构成回文，且这两个串覆盖整个串，因此 $S$ 是回文串。

根据结论2，回文自动机上 $x$ 节点在 $fail$ 树上的所有祖先都是 $x$ 对应串的Border。

在PAM上额外维护以下信息：

1. $dif_x=len_x-len_{fail_x}$ ，即 $x$ 与 $fail_x$ 最长Border的差，也就是所在等差数列的公差。

2. $anc_x$ 表示 $x$ 往上遇到的第一个 $dif_p\not=dif_{fail_p}$ 的 $p$ 的父亲，即所在等差数列的顶点的父亲。

   结论4：如果 $dif_x>{len_x\over 2}$ ，则 $anc_x=fail_x$ 。因为 $len_x$ 显然不可能再减一次 $dif_x$ 。

   结论5：如果 $dif_x=dif_{fail_x}$ ，则 $len_{fail_x}\ge{len_x\over 2}$ 。由结论4易得。

3. $sum_x$ 表示 $[x,anc_x)$ 路径上的当前信息（包含 $x$ ，不包含 $anc_x$ ）。

$sum$ 是动态维护的，某一时刻并不是所有 $sum$ 都有意义。假设当前插入了 $S[1,i]$ ，停在 $x$ 节点，则：

$$ sum_x=\sum\{f_{i-len_x},f_{i-len_{fail_x}},\cdots,f_{i-len_t}\},fail_t=anc_x $$

这样的话，我们只要不停的跳转 $x$ 到 $anc_x$ 就可以统计出 $f_i$ 答案，问题是如何维护。

接下来证明一个重要结论，按照上述过程，处理到 $x$ 时，$fail_x$（如果在路径上的话）一定已经在 $j=i-dif_x$ 时被处理过了。

$$ sum_{fail_x}=\sum\{f_{j-len_{fail_x}},\cdots,f_{j-len_t}\},fail_t=anc_x $$

首先证明，$fail_x$ 的最后一次出现位置在 $i-dif_x$ ：

由于 $fail_x$ 是 $x$ 的Border，因此 $i-dif_x$ 是一个出现位置，只需要证明 $[i-dif_x+1,i-1]$ 没有出现。

利用反证法：假设出现在了 $k$ ，根据结论5，$i-dif_x$ 的串和 $k$ 的串一定是接触的，则根据结论3，这两个串合起来也是回文串，且是 $x$ 的回文前缀即回文后缀，也就是说，$fail_x$ 并不是 $x$ 的最长回文后缀，这与定义不符，因此不存在 $k$ 。

接下来证明，$fail_x$ 一定在 $i-dif_x$ 时被更新过了：

假设在 $i-dif_x$ 时，存在一个 $fail_x$ 所在等差链的子节点 $p$ ，则 $fail_p=fail_x,len_p=len_{fail_x}+dif_x$ 。

即 $fail_x$ 往前添加 $dif_x$ 个字符之后是回文串，但是由于 $fail_x$ 是 $x$ 的回文前缀且长度也少 $dif_x$ ，根据Border和回文串的性质，易得 $x$ 往前添加 $dif_x$ 个字符也是回文串，这与当前处理到的 $x$ 定义不符（ $x$ 是链底或者 $x$ 是 $i$ 结尾的最长回文后缀）。

因此 $fail_x$ 一定是 $i-dif_x$ 时的链底（或者 $i-dif_x$ 的最长回文后缀），也就是说已经维护过了。

结论6：更新 $i$ 信息时，需要用到的 $sum$ 一定已经被更新过了。

我们观察 $sum_{fail_x}$ ，由于 $j=i-dif_x,len_x=len_{fail_x}+dif_x$ ，因此 $i-len_x=j-len_{fail_x}$ ，以此类推，$sum_{fail_x}$ 的所有项都在 $sum_x$ 中出现过，除了 $f_{i-len_t}$ ，因此只需要补上这一个即可，即：

$$ sum_x=sum_{fail_x}+f_{i-len_t},fail_t=anc_x $$

接下来说明复杂度：

结论7：$len_{anc_x}\le{len_x\over 2}$ 。由结论1可知，$x$ 到 $anc_x$ 时 $[2^k,2^{k+1})$ 的 $k$ 至少减一，因此长度至少减半。

因此 $x$ 沿着 $anc_x$ 只会跳 $\log_2n$ 次，更新 $sum$ 的复杂度为 $O(\log_2n)$ 。

对于这道题，由于只要偶数长度回文串，因此 $f_i$ 只允许偶数位置上有值。

示例程序

讲了这么多，代码就是PAM上加点东西，非常好写。

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000000,maxi=26,MOD=1e9+7;

int n;char s[maxn+5],t[maxn+5];
int pl,son[maxn+5][maxi],len[maxn+5],fai[maxn+5];
int dif[maxn+5],anc[maxn+5],sum[maxn+5];
int f[maxn+5];

inline int newnode() {pl++;return pl;}
int Extend(int p,char *s,int i){
    while (s[i]!=s[i-len[p]-1]) p=fai[p];
    if (!son[p][s[i]-'a']){
        int u=newnode(),k=fai[p];len[u]=len[p]+2;
        while (s[i]!=s[i-len[k]-1]) k=fai[k];
        fai[u]=son[k][s[i]-'a'];son[p][s[i]-'a']=u;
        dif[u]=len[u]-len[fai[u]];
        anc[u]=(dif[u]==dif[fai[u]]?anc[fai[u]]:fai[u]);
    }
    p=son[p][s[i]-'a'];
    return p;
}
inline int ADD(int x,int y) {return x+y>=MOD?x+y-MOD:x+y;}
int main(){
    scanf("%s",t+1);n=strlen(t+1);
    for (int i=1,L=1,R=n;i<=n;i+=2,L++,R--) s[i]=t[L],s[i+1]=t[R];
    pl=-1;newnode();newnode();
    fai[0]=fai[1]=1;len[0]=0;len[1]=-1;
    f[0]=1;
    for (int i=1,p=0;i<=n;i++){
        p=Extend(p,s,i);
        for (int x=p;x>1;x=anc[x]){
            sum[x]=f[i-(len[anc[x]]+dif[x])];
            if (dif[x]==dif[fai[x]]) sum[x]=ADD(sum[x],sum[fai[x]]);
            if (i&1^1) f[i]=ADD(f[i],sum[x]);
        }
    }
    printf("%d\n",f[n]);
    return 0;
}