№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
173278358 |
Дорешивание:
bkifhr9 |
1051E
- 25
|
C++14 (GCC 6-32)
|
Полное решение
|
62 мс
|
34256 КБ
|
2022-09-24 09:20:18 |
2022-09-24 09:20:18 |
|
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=998244353;
const int N=1e6+5;
char a[N],l[N],r[N];
int la,ll,lr;
LL dp[N],d[N];
int lcp[2][N],z1[N],z2[N];
void get_z(char s[],int len,int z[]){
int l=0,r=0;z[1]=len;
for(int i=2;i<=len;i++){
if(i<=r) z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]<=len&&s[i+z[i]]==s[z[i]+1]) z[i]++;
if(i+z[i]-1>r) r=i+z[i]-1,l=i;
}
}
void ex_kmp(char s[],int len,int z[],int p[]){
int l=0,r=0;
for(int i=1;i<=la;i++){
if(i<=r) p[i]=min(z[i-l+1],r-i+1);
while(i+p[i]<=la&&p[i]+1<=len&&a[i+p[i]]==s[p[i]+1]) p[i]++;
if(i+p[i]-1>r) r=i+p[i]-1,l=i;
}
}
int main(){
scanf("%s%s%s",(a+1),(l+1),(r+1));
la=strlen(a+1);ll=strlen(l+1);lr=strlen(r+1);
get_z(l,ll,z1),get_z(r,lr,z2);
ex_kmp(l,ll,z1,lcp[0]),ex_kmp(r,lr,z2,lcp[1]);
dp[la+1]=d[la+1]=1;
for(int i=la;i;i--){
if(a[i]=='0') dp[i]=(l[1]=='0'?dp[i+1]:0);
else{
int st=i+ll-1,ed=i+lr-1;
int x=lcp[0][i];
if(x<ll&&a[i+x]<l[x+1]) st++;
x=lcp[1][i];
if(x<lr&&a[i+x]>r[x+1]) ed--;
ed=min(ed,la);
if(st>ed) dp[i]=0;
else dp[i]=d[st+1]-d[ed+2];
}
dp[i]=(dp[i]+mod)%mod;
d[i]=d[i+1]+dp[i];
d[i]=(d[i]+mod)%mod;
}
printf("%lld",dp[1]);
return 0;
}
Время: ? ms, память: ? КБ