?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
43446806 |
Practice: WalkingDeade |
1051E - 25 | C++14 (GCC 6-32) | Accepted | 514 ms | 39080 KB | 2018-09-26 14:45:57 | 2018-09-26 14:45:57 |
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,m; const int maxn = 1e6+9; const int M = 998244353; int z1[2*maxn],z2[2*maxn]; long long dp[maxn]; string a,l,r,l2,r2; void cz(string &s,int z[2*maxn]) { int l=0,r=0; for (int i=1;i<s.size();i++) { if (i>r) { l = r = i; while (r<s.size() && s[r-l] == s[r]) r++; z[i] = r-l; r--; } else { int k = i-l; if (z[k] >= r-i+1) { l = i; while (r<s.size() && s[r-l] == s[r]) r++; z[i] = r-l; r--; } else z[i] = z[k]; } } } int main() { cin>>a>>l>>r; n = a.size(); l2 = l+'#'+a; r2 = r+'#'+a; cz(l2,z1); cz(r2,z2); dp[0] = 1; dp[1] = -1; for (int i=0;i<n;i++) { dp[i] = (dp[i] % M+M)%M; dp[i+1] += dp[i]; if (a[i] == '0') { if (l == "0") { dp[i+1] += dp[i]; dp[i+2] -= dp[i]; } continue; } int al=l.size()+1,ar=r.size()-1,zl=z1[l.size()+1+i],zr=z2[r.size()+1+i]; if (i+l.size()<=n && (zl==l.size() || a[i+zl]>l[zl])) al--; if (i+r.size()<=n && (zr==r.size()|| a[i+zr]<r[zr])) ar++; dp[min(i+al,n+1)] += dp[i]; dp[min(i+ar+1,n+1)] -= dp[i]; } cout<<(dp[n]%M+M)%M<<endl; return 0; }
?
?
?
?