General
 
 
# 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
→ Source
#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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details