fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6.  
  7. vector<int> Z(string s) {
  8.     int n = s.size();
  9.     vector<int> z(n, 0);
  10.     for (int i = 1, l = 0, r = 0; i < n; ++i) {
  11.         if (i <= r) z[i] = min(r - i + 1, z[i - l]);
  12.         while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
  13.         if (i + z[i] - 1 > r) r = i + z[i] - 1, l = i;
  14.     }
  15.     return z;
  16. }
  17.  
  18. const long long mod = 998244353;
  19. string a, l, r;
  20.  
  21. bool isaGreaterThan(int l, int r, string &b, vector<int> &zb) {
  22.     // return a[l..r] > b
  23.     if (r < l) return false;
  24.  
  25.     int len_b = b.size();
  26.     if (r - l + 1 < len_b) return false;
  27.     if (r - l + 1 > len_b) return true;
  28.  
  29.     int len = zb[len_b + l + 1];
  30.     if (len >= len_b) return false;
  31.     return a[l + len] > b[len];
  32. }
  33.  
  34. bool isaEqual(int l, int r, string &b, vector<int> &zb) {
  35.     // return a[l..r] == b
  36.     if (r < l) return false;
  37.     int len_b = b.size();
  38.     if (r - l + 1 != len_b) return false;
  39.     int len = zb[len_b + l + 1];
  40.     return (len >= len_b);
  41. }
  42.  
  43. void solve() {
  44.     cin >> a >> l >> r;
  45.  
  46.     vector<int> zl = Z(l + "#" + a);
  47.     vector<int> zr = Z(r + "#" + a);
  48.  
  49.     int n = a.size();
  50.     vector<long long> f(n + 5, 0), sum_suffix(n + 5, 0);
  51.     f[n] = sum_suffix[n] = 1;
  52.     int u = n, v = n - 1;
  53.     for (int i = n - 1; i >= 0; --i) {
  54.         if (a[i] == '0') {
  55.             f[i] = f[i + 1] * (l == "0");
  56.         }
  57.         else {
  58.             while (isaGreaterThan(i, u - 1, l, zl) || isaEqual(i, u - 1, l, zl)) --u;
  59.             while (isaGreaterThan(i, v, r, zr)) --v;
  60.             f[i] = (sum_suffix[u + 1] - sum_suffix[v + 2] + mod) % mod;
  61.         }
  62.         sum_suffix[i] = (sum_suffix[i + 1] + f[i]) % mod;
  63.     }
  64.     cout << f[0];
  65. }
  66.  
  67. int main() {
  68.     solve();
  69.     return 0;
  70. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/6Ohwwd
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!