# |
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 |
|
#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;
}
Click to see test details