www.luogu.com.cn
https://www.luogu.com.cn/problem/P11140
考虑 dp，设 fif_i 表示前 ii 个字符合法划分的方案数。
对于 ∀i\forall i，找到最小的 jj，满足 [j,i][j,i] 是有趣的，那么 fi←∑k=j−1i−1fkf_i \leftarrow \sum_{k=j-1}^{i-1} f_k，很明显这个有单调性，如果 [l,r][l,r] 有趣，那么对于 l≤i≤rl \le i \le r， [i,r][i,r] 肯定有趣，所以考虑用双指针维护 [j,i][j,i]
注意不要真的取模，会很慢，判断大于直接减掉就行
代码如下，时间复杂度 O(n)O(n)
#include<bits/stdc++.h>
using namespace std;
const int N=15000100,MOD=998244353;
int f[N],cnt,l=1,cc[N],sum;
char s[N];
signed main(){
cin.tie(0)->ios::sync_with_stdio(0);
cin>>s+1;
int n=strlen(s+1);
f[0]=1;
for(int r=1;r<=n;r++){
while(cnt&&l<r){
sum=s[l]-'0';
l++;
for(int k=l;k<=r;k++){
sum+=s[k]-'0';
cnt-=((cc[sum]--)==2);
}
}
sum=s[r+1]-'0';
for(int k=r;k>=l;k--){
f[r]+=f[k-1];
if(f[r]>=MOD) f[r]-=MOD;
sum+=s[k]-'0';
cnt+=((++cc[sum])==2);
}
}
cout<<f[n];
return 0;
}