题解归档 - cf932G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf932G
• 本地来源：problems/cf932G/idea.md
• 题目链接：https://codeforces.com/contest/932/problem/G
• 原始标题：cf932G — Palindrome Partition

思路

cf932G — Palindrome Partition

题意

给定偶长字符串 s，将其切成偶数段 p1,…,pk，要求 pi = p_{k-i+1}（段序列本身是回文）。求方案数 mod 1e9+7。

转化

构造 t = s1 s_n s2 s_{n-1} …（首尾交替取字符，|t|=|s|）。

结论：原串的合法划分 ↔ 对 t 做「偶数个回文串」的划分（每段是回文，段数为偶数）。

直觉：外层对称段 (p1,pk) 在 t 里对应一段偶长回文；向内递归同理。

DP

dp[i] = 前 i 个字符的合法划分方案数。

朴素：对每个以 i 结尾的回文后缀长度 len，dp[i] += dp[i-len]。

约束：段数必须为偶数 ⇒ 若 i 为奇数，强制 dp[i]=0。初始 dp[0]=1。

回文自动机优化

对每个位置 i，以 i 结尾的所有回文后缀在 PAM 上形成 O(log n) 条「等差长度链」（border/周期性质）。

对每个结点 v 维护：

• dif(v) = len(v) - len(fa(v))
• slk(v)：沿 fail 向上第一个 dif 不同的祖先
• f(v)：当前等差链在「最后更新位置」上的 dp 贡献和

转移（沿 slk 跳，最多 O(log n) 次）：

f(v) = dp[i - slk(v).len - dif(v)]
若 slk(v) != fa(v)：f(v) += fa(v).f
dp[i] += f(v)

复杂度

• 时间 O(n log n)
• 空间 O(n)

验证

• 样例 abcdcdab → 1，abbababababbab → 3
• 与暴力（递归匹配首尾相等前缀/后缀）对拍 70+ 小数据无分歧（Kali SSH 中断前）

参考

• 博客园题解

代码

来源：problems/cf932G/solution.cpp

/* Author: likely
 * Time: 2026-06-08 03:29:27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1000005;
const ll mod=1000000007;
struct node{
    ll len,dif,f;
    node *slk,*ch[26],*fa;
};
node pl[maxn+5],*rt1,*rt2,*ncnt;
node *nd[maxn+5];
char s[maxn+5],t[maxn+5];
ll dp[maxn+5],i,j,k,len;
void build(char *S,ll n){
    rt1=ncnt=pl;
    rt2=(++ncnt);
    rt2->fa=rt1;
    rt1->len=-1;
    rt2->len=0;
    node *pre=rt1;
    for(i=0;i<n;i++){
        while(S[i]!=S[i-pre->len-1]) pre=pre->fa;
        if(pre->ch[S[i]-'a']==nullptr){
            node *q=(++ncnt);
            q->len=pre->len+2;
            if(pre==rt1) q->fa=rt2;
            else{
                node *p=pre->fa;
                while(S[i]!=S[i-p->len-1]) p=p->fa;
                q->fa=p->ch[S[i]-'a'];
            }
            q->dif=q->len-q->fa->len;
            q->slk=(q->dif==q->fa->dif?q->fa->slk:q->fa);
            pre->ch[S[i]-'a']=q;
        }
        nd[i+1]=pre=pre->ch[S[i]-'a'];
    }
}
int main(){
    scanf("%s",s);
    len=strlen(s);
    for(i=0;i<len/2;i++){
        t[(i<<1)+1]=s[i];
        t[(i<<1|1)+1]=s[len-i-1];
    }
    build(t+1,len);
    dp[0]=1;
    for(i=1;i<=len;i++){
        node *p=nd[i];
        while(p!=rt2){
            p->f=dp[i-p->slk->len-p->dif];
            if(p->slk!=p->fa) p->f=(p->f+p->fa->f)%mod;
            dp[i]=(dp[i]+p->f)%mod;
            p=p->slk;
        }
        if(i&1) dp[i]=0;
    }
    printf("%lld\n",dp[len]);
    return 0;
}