№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
181056319 |
Дорешивание:
bkifhr8 |
1051E
- 25
|
C++20 (GCC 11-64)
|
Полное решение
|
139 мс
|
29340 КБ
|
2022-11-15 11:33:29 |
2022-11-15 11:33:29 |
|
#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
*/
Время: ? ms, память: ? КБ