题解：P11140 [APC001] E - Linear Map
考虑 dp，设 fi 表示前 i 个字符合法划分的方案数。
对于 ∀i，找到最小的 j，满足 [j,i] 是有趣的，那么 fi←∑k=j−1i−1fk，很明显这个有单调性，如果 [l,r] 有趣，那么对于 l≤i≤r， [i,r] 肯定有趣，所以考虑用双指针维护 [j,i]
注意不要真的取模，会很慢，判断大于直接减掉就行
代码如下，时间复杂度 O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #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;
}
|
