General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
141321916 Practice:
bkifhr9
1051E - 25 C++14 (GCC 6-32) Accepted 61 ms 26456 KB 2022-01-01 17:19:12 2022-01-01 17:19:12
→ Source
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int z[1001000];
void FK(char *f,char *g,int *a,int n,int m){
	z[1]=m;
	for(int i=2,l=0,r=0;i<=m;i++){
		z[i]=0;
		if(i<=r)z[i]=min(r-i+1,z[i-l+1]);
		while(g[i+z[i]]==g[1+z[i]])z[i]++;
		if(i+z[i]-1>r)r=i+z[i]-1,l=i;
	}
	for(int i=1,l=0,r=0;i<=n;i++){
		int now=0;
		if(i<=r)now=min(r-i+1,z[i-l+1]);
		while(f[i+now]==g[1+now])now++;
		a[i]=now;
		if(i+now-1>r)r=i+now-1,l=i;
	}
}
char l[1001000],r[1001000],c[1000100];
int n,L,R,dp[1001000],s[1001000],tag[1001000];
int a[1001000],b[1001000];
int main(){
	scanf("%s%s%s",c+1,l+1,r+1);L=strlen(l+1),R=strlen(r+1),n=strlen(c+1);
	FK(c,l,a,n,L);FK(c,r,b,n,R);
	dp[0]=1;int nowf=0,l1=0,r1=0,l2=0,r2=0;
	for(int i=0;i<n;i++){
		if(c[i+1]=='0'){if(L==1&&l[1]=='0')(tag[i+1]+=dp[i])%=mod,(tag[i+2]-=dp[i])%=mod; }
		else{
			bool f1=(a[i+1]>=L||i+1+a[i+1]<=n&&l[1+a[i+1]]<c[i+1+a[i+1]]),f2=(b[i+1]>=R||i+1+b[i+1]>n||r[1+b[i+1]]>c[i+1+b[i+1]]);
			if(L<R){
				(tag[i+L+!f1]+=dp[i])%=mod;
				(tag[i+R+f2]-=dp[i])%=mod;
			}
			else if(f1&&f2)(tag[i+L]+=dp[i])%=mod,(tag[i+L+1]-=dp[i])%=mod;
		}
		(nowf+=tag[i+1])%=mod,dp[i+1]=nowf;
	}
	return printf("%d",(dp[n]+mod)%mod),0;
}
		  	 		 	 			 			  	  			   	
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details