题解：P11140 [APC001] E - Linear Map
Luogu P11140 [APC001] E - Linear Map 题解
考虑 dp，设 $f_i$ 表示前 $i$ 个字符合法划分的方案数。
对于 $\forall i$，找到最小的 $j$，满足 $[j,i]$ 是有趣的，那么 $f_i \leftarrow \sum_{k=j-1}^{i-1} f_k$，很明显这个有单调性，如果 $[l,r]$ 有趣，那么对于 $l \le i \le 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;
}
|
