题解：P11140 [APC001] E - Linear Map

www.luogu.com.cn

https://www.luogu.com.cn/problem/P11140

考虑 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)$

cpp

#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; 
}

题解：P11140 [APC001] E - Linear Map

评论