?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
172816087 |
Practice: luogu_bot2 |
1051E - 25 | C++14 (GCC 6-32) | Accepted | 46 ms | 29364 KB | 2022-09-20 13:48:17 | 2022-09-20 13:48:18 |
#include <bits/stdc++.h> using namespace std; const int N=2e6+10, mod=998244353; int n, l1, l2, b[N], c[N], s[N], f, tf; char a[N], l[N], r[N]; void calc(char *x, int len, int *t) { for (int i=1, l=1, r=0; i<len; i++) { if (i<=r) t[i]=min(t[i-l], r-i+1); while (i+t[i]<len && x[t[i]]==x[i+t[i]]) t[i]++; if (r<i+t[i]) l=i, r=i+t[i]-1; } } int main() { scanf("%s%s%s", a, l, r); n=strlen(a), l1=strlen(l), l2=strlen(r); l[l1]=r[l2]='*'; for (int i=0; i<n; i++) l[l1+i+1]=r[l2+i+1]=a[i]; calc(l, n+l1+1, b), calc(r, n+l2+1, c); for (int i=0; i<l1; i++) s[i]=1; for (int i=l1; i<=n; i++) { int L, R; if (i<l2) L=-1; else if (c[i+1]==l2 || r[c[i+1]]>a[i-l2+c[i+1]]) L=i-l2-1; else L=i-l2; if (b[i+1]==l1 || l[b[i+1]]<=a[i-l1+b[i+1]]) R=i-l1; else R=i-l1-1; if (R==-1 || L>R) 1+1==2; else if (L==-1) f=s[R]; else f=(s[R]-s[L]+mod)%mod; if (l[0]=='0' && l1==1) f=(f+tf)%mod, tf=0; s[i]=s[i-1]; if (a[i]=='0') tf=f; else s[i]=(s[i]+f)%mod; } printf("%d\n", f); return 0; } /* ACedddd */
?
?
?
?