General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
103610165 Practice:
mrsrz
1051E - 25 C++17 (GCC 7-32) Accepted 62 ms 24472 KB 2021-01-07 11:02:54 2021-01-07 11:02:54
→ Source
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2,md=998244353;
char s[N],L[N],R[N],t[2*N];
int n,lenL,lenR,_L[2*N],_R[2*N],dp[N];
void Z(char*s,int*z,int n){
	z[1]=n;
	for(int i=2,l=0,r=0;i<=n;++i){
		if(i<=r)z[i]=min(r-i+1,z[i-l+1]);
		while(i+z[i]<=n&&s[i+z[i]]==s[1+z[i]])++z[i];
		if(i+z[i]-1>r)l=i,r=i+z[i]-1;
	}
}
inline void upd(int&a){a+=a>>31&md;}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>(s+1)>>(L+1)>>(R+1);
	n=strlen(s+1),lenL=strlen(L+1),lenR=strlen(R+1);
	strcpy(t+1,L+1),strcat(t+1,s+1);
	Z(t,_L,n+lenL);
	for(int i=1;i<=n;++i)
	_L[i]=min(_L[i+lenL],lenL);
	strcpy(t+1,R+1),strcat(t+1,s+1);
	Z(t,_R,n+lenR);
	for(int i=1;i<=n;++i)
	_R[i]=min(_R[i+lenR],lenR);
	dp[0]=1,dp[1]=md-1;
	for(int i=1;i<=n;++i){
		int l=lenL+1,r=lenR-1;
		if(i+lenL-1<=n&&(_L[i]==lenL||L[_L[i]+1]<s[i+_L[i]]))--l;
		if(i+lenR-1<=n&&(_R[i]==lenR||R[_R[i]+1]>s[i+_R[i]]))++r;
		r=min(r,n-i+1);
		if(s[i]=='0')r=1,l=L[1]=='0'?1:2;
		if(i+l-1<=n)upd(dp[i+l-1]+=dp[i-1]-md),upd(dp[i+r]-=dp[i-1]);
		upd(dp[i]+=dp[i-1]-md);
	}
	cout<<dp[n]<<'\n';
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details