?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
139506718 |
Practice: nguyenhaan2209 |
1051E - 25 | C++20 (GCC 11-64) | Accepted | 171 ms | 44976 KB | 2021-12-16 17:12:57 | 2021-12-16 17:12:57 |
#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; }
?
?
?
?