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