?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
192576514 |
Practice: Azimjonm0012 |
1051E - 25 | C++17 (GCC 7-32) | Accepted | 46 ms | 26456 KB | 2023-02-07 12:05:53 | 2023-02-07 12:05:53 |
#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; }
?
?
?
?