General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
173431732 Practice:
bkifhr7
1051E - 25 C++14 (GCC 6-32) Accepted 46 ms 34256 KB 2022-09-25 16:25:43 2022-09-25 16:25:43
→ Source
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+2,P=998244353;
char a[N],l[N],r[N];
int za[N],zl[N],zr[N];
int pa[N],pl[N],pr[N];
int f[N],sum[N];
int lena,lenl,lenr;
void Z(char s[],int len,int z[]){
	int l=0,r=0;
	z[1]=len;
	for(int i=2;i<=len;i++){
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=len&&s[i+z[i]]==s[z[i]+1]) z[i]++;
		if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}
}
void exkmp(char s[],int len,int z[],int p[]){
	int l=0,r=0;
	for(int i=1;i<=lena;i++){
		if(i<=r)p[i]=min(z[i-l+1],r-i+1);
		while(i+p[i]<=lena&&p[i]+1<=len&&a[i+p[i]]==s[p[i]+1]) p[i]++;
		if(i+p[i]-1>r)r=i+p[i]-1,l=i;
	}
}
int main(){
	scanf("%s%s%s",a+1,l+1,r+1);
	lena=strlen(a+1),lenl=strlen(l+1),lenr=strlen(r+1);
	Z(l,lenl,zl),exkmp(l,lenl,zl,pl);
	Z(r,lenr,zr),exkmp(r,lenr,zr,pr);
	f[lena+1]=sum[lena+1]=1;
	for(int i=lena;i>=1;i--){
		if(a[i]=='0'){
			if(l[1]=='0')f[i]=f[i+1];
			else f[i]=0;
		}else{
			int ll=pl[i],lr=pr[i];
			int L=i+lenl-1,R=i+lenr-1;
			if(ll<lenl&&a[i+ll]<l[ll+1])L++;
			if(lr<lenr&&a[i+lr]>r[lr+1])R--;
			R=min(R,lena);
			if(L>R) f[i]=0;
			else f[i]=(sum[L+1]-sum[R+1+1]+P)%P;
		}
		sum[i]=(f[i]+sum[i+1])%P;
	}
	printf("%d",f[1]);
	return 0;
}

 	 	    	  	    		  				 		   	
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details