题解：CF2205E Simons and Dividing the Rhythm

libu2333 · 2026-10-18 17:29:12 · 题解

退役一年忘了 KMP 怎么写，痛失 100pts。

首先我们注意到，统计有多少个 S 能变成 T，等价于统计对 T 做一次任意分段翻转能得到多少种不同结果。

所以我们设 f_i 表示前缀 T_{1\sim i} 经分段翻转后的不同结果数。显然 f_0=1。

然后我们发现去重这个问题不是很好办。经过思考，我们发现如果最后一段形如 ABA，将其整体翻转与把三个部分分别翻转会得到同一结果，所以我们钦定最后一段一定是不存在非平凡 border 的，这样就达到了去重的效果。

所以我们枚举最后一段 T_{l\sim r}，若它不存在非平凡 border，则 f_r \gets f_r+f_{l-1}。

那么如何判断这一段不存在非平凡 border 呢？我们可以一边 DP 一边使用 KMP 快速计算前缀函数，这样时间复杂度就变成 O(n^2) 了。

代码如下。

#include<bits/stdc++.h>
#define MOD 998244353
using namespace std;
int a[8005],dp[8005];
int nxt[8005],n;
int mian(){
    memset(nxt,0,sizeof nxt);
    memset(dp,0,sizeof dp);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[0]=1;
    for(int i=1;i<=n;i++){
        int m=n-i+1;
        nxt[0]=-1;     
        for(int j=0,k=-1;j<m;){
            if(k==-1||a[i+j]==a[i+k]) nxt[++j]=++k;
            else k=nxt[k];
        }
        for(int j=1;j<=m;j++){
            if(nxt[j]==0){
                int r=i+j-1;
                dp[r]=(dp[r]+dp[i-1])%MOD;
            }
        }
    }
    cout<<dp[n]<<'\n';
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin>>T;
    while(T--) mian();
}