www.luogu.com.cn
https://www.luogu.com.cn/problem/P11140
考虑 dp，设 表示前 个字符合法划分的方案数。
对于 ，找到最小的 ，满足 是有趣的，那么 ，很明显这个有单调性，如果 有趣，那么对于 ， 肯定有趣，所以考虑用双指针维护
注意不要真的取模，会很慢，判断大于直接减掉就行
代码如下，时间复杂度
#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;
}