General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
185265311 Practice:
Pray2018
1051E - 25 C++17 (GCC 9-64) Accepted 124 ms 44992 KB 2022-12-15 11:52:21 2022-12-15 11:52:21
→ Source
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,M=998244353;
char s[N],L[N],R[N];
int n,sl,sr,a[N],b[N],dp[N],sum[N],l,r;
void exkmp(char *s,char *t,int *g){
	int n=strlen(s+1),m=strlen(t+1);
	s[++n]='#';
	for (int i=1;i<=m;i++)s[++n]=t[i];
	int k=1,f[N];
	f[1]=0;
	for (int i=2;i<=n;i++){
		f[i]=max(0,min(k+f[k]-i,f[i-k+1]));
		while (i+f[i]<=n&&s[i+f[i]]==s[f[i]+1])f[i]++;
		if (f[i]+i>f[k]+k) k=i;
	}
	for (int i=m,j=n;i>=1;i--,j--)g[i]=f[j];
}
int main(){
	scanf("%s%s%s",s+1,L+1,R+1);
	n=strlen(s+1);sl=strlen(L+1);sr=strlen(R+1);
	exkmp(L,s,a);exkmp(R,s,b);
	sum[0]=dp[0]=1;
	for (int i=1;i<=n;i++){
		if (i>=sl){
			l=0,r=i-sl;
			if (a[r+1]<sl&&s[r+a[r+1]+1]<L[a[r+1]+1])r--;
			if (i>=sr){
				l=i-sr;
				if (b[l+1]<sr&&s[l+b[l+1]+1]>R[b[l+1]+1])l++;
			}
			if (l<=r){
				(dp[i]+=sum[r])%=M;
				if (l)(dp[i]+=M-sum[l-1])%=M;
			}
			if (L[1]=='0'&&s[i]=='0')(dp[i]+=dp[i-1])%=M;
		}
		sum[i]=sum[i-1];
		if (i<n&&s[i+1]!='0')(sum[i]+=dp[i])%=M;
	}
	printf("%d\n",dp[n]);
	return 0;
}

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