test/verify/yosupo-number-of-increasing-sequences-between-two-sequences.test.cpp

• View this file on GitHub
• Last update: 2026-08-02 17:14:47+00:00
• Problem: https://judge.yosupo.jp/problem/number_of_increasing_sequences_between_two_sequences

Depends on

• Count Bounded Increasing Sequences (math/combinatorics/count-bounded-increasing-sequences.hpp)
• Enumeration (組み合わせ) (math/combinatorics/enumeration.hpp)
• Montgomery Mod Int (math/combinatorics/montgomery-mod-int.hpp)
• Number Theoretic Transform Friendly ModInt (math/fft/number-theoretic-transform-friendly-mod-int.hpp)
• Scanner(高速入力) (other/scanner.hpp)
• template/template.hpp

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/number_of_increasing_sequences_between_two_sequences

#include "../../template/template.hpp"

#include "../../math/combinatorics/count-bounded-increasing-sequences.hpp"
#include "../../math/combinatorics/montgomery-mod-int.hpp"
#include "../../other/scanner.hpp"

using mint = modint998244353;

int main() {
  Scanner input(stdin);
  int N, M;
  input.read(N, M);
  vector< int > A(N), B(N);
  input.read(A, B);
  cout << count_bounded_increasing_sequences< mint >(A, B).val() << endl;
}

#line 1 "test/verify/yosupo-number-of-increasing-sequences-between-two-sequences.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/number_of_increasing_sequences_between_two_sequences

#line 1 "template/template.hpp"
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}

template <typename T1, typename T2>
bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T& t, const V& v) {
  t = v;
}

template <typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T& t, const V& v) {
  for (auto& e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F&& f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
decltype(auto) MFP(F&& f) {
  return FixPoint<F>{std::forward<F>(f)};
}
#line 4 "test/verify/yosupo-number-of-increasing-sequences-between-two-sequences.test.cpp"

#line 2 "math/combinatorics/count-bounded-increasing-sequences.hpp"

#line 1 "math/fft/number-theoretic-transform-friendly-mod-int.hpp"
/**
 * @brief Number Theoretic Transform Friendly ModInt
 */
template <typename Mint>
struct NumberTheoreticTransformFriendlyModInt {
  static vector<Mint> roots, iroots, rate2, irate2, rate3, irate3;
  static int max_base;

  NumberTheoreticTransformFriendlyModInt() = default;

  static void init() {
    if (roots.empty()) {
      const unsigned mod = Mint::mod();
      assert(mod >= 3 && mod % 2 == 1);
      auto tmp = mod - 1;
      max_base = 0;
      while (tmp % 2 == 0) tmp >>= 1, max_base++;
      Mint root = 2;
      while (root.pow((mod - 1) >> 1) == 1) {
        root += 1;
      }
      assert(root.pow(mod - 1) == 1);

      roots.resize(max_base + 1);
      iroots.resize(max_base + 1);
      rate2.resize(max_base + 1);
      irate2.resize(max_base + 1);
      rate3.resize(max_base + 1);
      irate3.resize(max_base + 1);

      roots[max_base] = root.pow((mod - 1) >> max_base);
      iroots[max_base] = Mint(1) / roots[max_base];
      for (int i = max_base - 1; i >= 0; i--) {
        roots[i] = roots[i + 1] * roots[i + 1];
        iroots[i] = iroots[i + 1] * iroots[i + 1];
      }
      {
        Mint prod = 1, iprod = 1;
        for (int i = 0; i <= max_base - 2; i++) {
          rate2[i] = roots[i + 2] * prod;
          irate2[i] = iroots[i + 2] * iprod;
          prod *= iroots[i + 2];
          iprod *= roots[i + 2];
        }
      }
      {
        Mint prod = 1, iprod = 1;
        for (int i = 0; i <= max_base - 3; i++) {
          rate3[i] = roots[i + 3] * prod;
          irate3[i] = iroots[i + 3] * iprod;
          prod *= iroots[i + 3];
          iprod *= roots[i + 3];
        }
      }
    }
  }

  static void ntt(vector<Mint>& a) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    int h = __builtin_ctz(n);
    assert(h <= max_base);
    int len = 0;
    Mint imag = roots[2];
    if (h & 1) {
      int p = 1 << (h - 1);
      for (int i = 0; i < p; i++) {
        auto r = a[i + p];
        a[i + p] = a[i] - r;
        a[i] += r;
      }
      len++;
    }
    for (; len + 1 < h; len += 2) {
      int p = 1 << (h - len - 2);
      {  // s = 0
        for (int i = 0; i < p; i++) {
          auto a0 = a[i];
          auto a1 = a[i + p];
          auto a2 = a[i + 2 * p];
          auto a3 = a[i + 3 * p];
          auto a1na3imag = (a1 - a3) * imag;
          auto a0a2 = a0 + a2;
          auto a1a3 = a1 + a3;
          auto a0na2 = a0 - a2;
          a[i] = a0a2 + a1a3;
          a[i + 1 * p] = a0a2 - a1a3;
          a[i + 2 * p] = a0na2 + a1na3imag;
          a[i + 3 * p] = a0na2 - a1na3imag;
        }
      }
      Mint rot = rate3[0];
      for (int s = 1; s < (1 << len); s++) {
        int offset = s << (h - len);
        Mint rot2 = rot * rot;
        Mint rot3 = rot2 * rot;
        for (int i = 0; i < p; i++) {
          auto a0 = a[i + offset];
          auto a1 = a[i + offset + p] * rot;
          auto a2 = a[i + offset + 2 * p] * rot2;
          auto a3 = a[i + offset + 3 * p] * rot3;
          auto a1na3imag = (a1 - a3) * imag;
          auto a0a2 = a0 + a2;
          auto a1a3 = a1 + a3;
          auto a0na2 = a0 - a2;
          a[i + offset] = a0a2 + a1a3;
          a[i + offset + 1 * p] = a0a2 - a1a3;
          a[i + offset + 2 * p] = a0na2 + a1na3imag;
          a[i + offset + 3 * p] = a0na2 - a1na3imag;
        }
        rot *= rate3[__builtin_ctz(~s)];
      }
    }
  }

  static void intt(vector<Mint>& a, bool f = true) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    int h = __builtin_ctz(n);
    assert(h <= max_base);
    int len = h;
    Mint iimag = iroots[2];
    for (; len > 1; len -= 2) {
      int p = 1 << (h - len);
      {  // s = 0
        for (int i = 0; i < p; i++) {
          auto a0 = a[i];
          auto a1 = a[i + 1 * p];
          auto a2 = a[i + 2 * p];
          auto a3 = a[i + 3 * p];
          auto a2na3iimag = (a2 - a3) * iimag;
          auto a0na1 = a0 - a1;
          auto a0a1 = a0 + a1;
          auto a2a3 = a2 + a3;
          a[i] = a0a1 + a2a3;
          a[i + 1 * p] = (a0na1 + a2na3iimag);
          a[i + 2 * p] = (a0a1 - a2a3);
          a[i + 3 * p] = (a0na1 - a2na3iimag);
        }
      }
      Mint irot = irate3[0];
      for (int s = 1; s < (1 << (len - 2)); s++) {
        int offset = s << (h - len + 2);
        Mint irot2 = irot * irot;
        Mint irot3 = irot2 * irot;
        for (int i = 0; i < p; i++) {
          auto a0 = a[i + offset];
          auto a1 = a[i + offset + 1 * p];
          auto a2 = a[i + offset + 2 * p];
          auto a3 = a[i + offset + 3 * p];
          auto a2na3iimag = (a2 - a3) * iimag;
          auto a0na1 = a0 - a1;
          auto a0a1 = a0 + a1;
          auto a2a3 = a2 + a3;
          a[i + offset] = a0a1 + a2a3;
          a[i + offset + 1 * p] = (a0na1 + a2na3iimag) * irot;
          a[i + offset + 2 * p] = (a0a1 - a2a3) * irot2;
          a[i + offset + 3 * p] = (a0na1 - a2na3iimag) * irot3;
        }
        irot *= irate3[__builtin_ctz(~s)];
      }
    }
    if (len >= 1) {
      int p = 1 << (h - 1);
      for (int i = 0; i < p; i++) {
        auto ajp = a[i] - a[i + p];
        a[i] += a[i + p];
        a[i + p] = ajp;
      }
    }
    if (f) {
      Mint inv_sz = Mint(1) / n;
      for (int i = 0; i < n; i++) a[i] *= inv_sz;
    }
  }

  /**
   * @brief Transpose of ntt()
   */
  static void transposed_ntt(vector<Mint>& a) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    const int h = __builtin_ctz(n);
    assert(h <= max_base);

    int len = h;
    const Mint imag = roots[2];
    while (len > 0) {
      if (len == 1) {
        const int p = 1 << (h - len);
        Mint rot = 1;
        for (int s = 0; s < (1 << (len - 1)); s++) {
          const int offset = s << (h - len + 1);
          for (int i = 0; i < p; i++) {
            const auto lhs = a[i + offset];
            const auto rhs = a[i + offset + p];
            a[i + offset] = lhs + rhs;
            a[i + offset + p] = (lhs - rhs) * rot;
          }
          rot *= rate2[__builtin_ctz(~s)];
        }
        len--;
      } else {
        const int p = 1 << (h - len);
        Mint rot = 1;
        for (int s = 0; s < (1 << (len - 2)); s++) {
          const int offset = s << (h - len + 2);
          const Mint rot2 = rot * rot;
          const Mint rot3 = rot2 * rot;
          for (int i = 0; i < p; i++) {
            const auto a0 = a[i + offset];
            const auto a1 = a[i + offset + p];
            const auto a2 = a[i + offset + 2 * p];
            const auto a3 = a[i + offset + 3 * p];
            const auto x = (a2 - a3) * imag;
            a[i + offset] = a0 + a1 + a2 + a3;
            a[i + offset + p] = (a0 - a1 + x) * rot;
            a[i + offset + 2 * p] = (a0 + a1 - a2 - a3) * rot2;
            a[i + offset + 3 * p] = (a0 - a1 - x) * rot3;
          }
          rot *= rate3[__builtin_ctz(~s)];
        }
        len -= 2;
      }
    }
  }

  /**
   * @brief Transpose of intt()
   */
  static void transposed_intt(vector<Mint>& a, bool f = true) {
    init();
    const int n = (int)a.size();
    assert((n & (n - 1)) == 0);
    const int h = __builtin_ctz(n);
    assert(h <= max_base);

    if (f) {
      const Mint inv_sz = Mint(1) / n;
      for (auto& value : a) value *= inv_sz;
    }

    int len = 0;
    const Mint iimag = iroots[2];
    while (len < h) {
      if (len == h - 1) {
        const int p = 1 << (h - len - 1);
        Mint irot = 1;
        for (int s = 0; s < (1 << len); s++) {
          const int offset = s << (h - len);
          for (int i = 0; i < p; i++) {
            const auto lhs = a[i + offset];
            const auto rhs = a[i + offset + p] * irot;
            a[i + offset] = lhs + rhs;
            a[i + offset + p] = lhs - rhs;
          }
          irot *= irate2[__builtin_ctz(~s)];
        }
        len++;
      } else {
        const int p = 1 << (h - len - 2);
        Mint irot = 1;
        for (int s = 0; s < (1 << len); s++) {
          const Mint irot2 = irot * irot;
          const Mint irot3 = irot2 * irot;
          const int offset = s << (h - len);
          for (int i = 0; i < p; i++) {
            const auto a0 = a[i + offset];
            const auto a1 = a[i + offset + p] * irot;
            const auto a2 = a[i + offset + 2 * p] * irot2;
            const auto a3 = a[i + offset + 3 * p] * irot3;
            const auto x = (a1 - a3) * iimag;
            a[i + offset] = a0 + a2 + a1 + a3;
            a[i + offset + p] = a0 + a2 - a1 - a3;
            a[i + offset + 2 * p] = a0 - a2 + x;
            a[i + offset + 3 * p] = a0 - a2 - x;
          }
          irot *= irate3[__builtin_ctz(~s)];
        }
        len += 2;
      }
    }
  }

  static vector<Mint> multiply(vector<Mint> a, vector<Mint> b) {
    int need = a.size() + b.size() - 1;
    int nbase = 1;
    while ((1 << nbase) < need) nbase++;
    int sz = 1 << nbase;
    a.resize(sz, 0);
    b.resize(sz, 0);
    ntt(a);
    ntt(b);
    Mint inv_sz = Mint(1) / sz;
    for (int i = 0; i < sz; i++) a[i] *= b[i] * inv_sz;
    intt(a, false);
    a.resize(need);
    return a;
  }
};

template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::roots =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::iroots =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::rate2 =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::irate2 =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::rate3 =
    vector<Mint>();
template <typename Mint>
vector<Mint> NumberTheoreticTransformFriendlyModInt<Mint>::irate3 =
    vector<Mint>();
template <typename Mint>
int NumberTheoreticTransformFriendlyModInt<Mint>::max_base = 0;
#line 1 "math/combinatorics/enumeration.hpp"
/**
 * @brief Enumeration(組み合わせ)
 */
template <typename T>
struct Enumeration {
 private:
  static vector<T> _fact, _finv, _inv;

  inline static void expand(size_t sz) {
    if (_fact.size() < sz + 1) {
      int pre_sz = max(1, (int)_fact.size());
      _fact.resize(sz + 1, T(1));
      _finv.resize(sz + 1, T(1));
      _inv.resize(sz + 1, T(1));
      for (int i = pre_sz; i <= (int)sz; i++) {
        _fact[i] = _fact[i - 1] * T(i);
      }
      _finv[sz] = T(1) / _fact[sz];
      for (int i = (int)sz - 1; i >= pre_sz; i--) {
        _finv[i] = _finv[i + 1] * T(i + 1);
      }
      for (int i = pre_sz; i <= (int)sz; i++) {
        _inv[i] = _finv[i] * _fact[i - 1];
      }
    }
  }

 public:
  explicit Enumeration(size_t sz = 0) { expand(sz); }

  static inline T fact(int k) {
    expand(k);
    return _fact[k];
  }

  static inline T finv(int k) {
    expand(k);
    return _finv[k];
  }

  static inline T inv(int k) {
    expand(k);
    return _inv[k];
  }

  static T P(int n, int r) {
    if (r < 0 || n < r) return 0;
    return fact(n) * finv(n - r);
  }

  static T C(int p, int q) {
    if (q < 0 || p < q) return 0;
    return fact(p) * finv(q) * finv(p - q);
  }

  static T H(int n, int r) {
    if (n < 0 || r < 0) return 0;
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};

template <typename T>
vector<T> Enumeration<T>::_fact = vector<T>();
template <typename T>
vector<T> Enumeration<T>::_finv = vector<T>();
template <typename T>
vector<T> Enumeration<T>::_inv = vector<T>();
#line 5 "math/combinatorics/count-bounded-increasing-sequences.hpp"

/**
 * @brief Count Bounded Increasing Sequences
 */
template <typename Mint>
Mint count_bounded_increasing_sequences(const vector<int>& lower_bounds,
                                        const vector<int>& upper_bounds) {
  using NTT = NumberTheoreticTransformFriendlyModInt<Mint>;

  assert(lower_bounds.size() == upper_bounds.size());
  const int original_n = static_cast<int>(upper_bounds.size());
  if (original_n == 0) return Mint(1);

  vector<int> lower(lower_bounds), upper(upper_bounds);
  for (int i = 0; i < original_n; i++) {
    assert(lower[i] >= 0);
    assert(upper[i] >= 0);
    if (i > 0) lower[i] = max(lower[i], lower[i - 1]);
  }
  for (int i = original_n - 1; i-- > 0;) {
    upper[i] = min(upper[i], upper[i + 1]);
  }
  for (int i = 0; i < original_n; i++) {
    if (lower[i] >= upper[i]) return Mint(0);
    --upper[i];
  }

  // Shift the lower boundary one column to the right and translate by L[0].
  const int base = lower[0];
  const int n = original_n + 1;
  vector<int> lower_boundary(n), upper_boundary(n);
  lower_boundary[0] = 0;
  for (int i = 0; i < original_n; i++) {
    lower_boundary[i + 1] = lower[i] - base;
    upper_boundary[i] = upper[i] - base;
  }
  // A terminal vertical edge. The extra height does not change the answer.
  upper_boundary[original_n] = upper.back() - base + 1;

  const int max_factorial = n + upper_boundary.back() + 5;
  assert(static_cast<uint64_t>(max_factorial) < Mint::mod());
  Enumeration<Mint> enumeration(max_factorial);

  // Compute only the first `limit` coefficients.
  auto convolution_prefix = [&](vector<Mint> f, vector<Mint> g, int limit) {
    assert(limit >= 0);
    if (limit == 0) return vector<Mint>();
    assert(!f.empty() && !g.empty());
    if (static_cast<int>(f.size()) > limit) f.resize(limit);
    if (static_cast<int>(g.size()) > limit) g.resize(limit);

    if (min(f.size(), g.size()) <= 32) {
      vector<Mint> result(limit);
      for (int i = 0; i < static_cast<int>(f.size()); i++) {
        if (f[i] == Mint(0)) continue;
        const int m = min<int>(static_cast<int>(g.size()), limit - i);
        for (int j = 0; j < m; j++) result[i + j] += f[i] * g[j];
      }
      return result;
    }

    auto result = NTT::multiply(std::move(f), std::move(g));
    result.resize(limit);
    return result;
  };

  auto propagate_rectangle = [&](const vector<Mint>& left_edge,
                                 const vector<Mint>& bottom_edge) {
    const int height = static_cast<int>(left_edge.size());
    const int width = static_cast<int>(bottom_edge.size());
    assert(width > 0);
    if (height == 0) {
      return make_pair(bottom_edge, vector<Mint>());
    }

    vector<Mint> top_edge(width), right_edge(height);
    const bool has_left = any_of(left_edge.begin(), left_edge.end(),
                                 [](const Mint& x) { return x != Mint(0); });
    const bool has_bottom = any_of(bottom_edge.begin(), bottom_edge.end(),
                                   [](const Mint& x) { return x != Mint(0); });

    // Left -> top and bottom -> right are middle products with the same
    // factorial kernel. A cyclic convolution of length >= height + width - 1
    // computes the required middle coefficients without wraparound.
    if (has_left || has_bottom) {
      if (min(height, width) <= 32) {
        if (has_left) {
          vector<Mint> scaled(height);
          for (int k = 0; k < height; k++) {
            scaled[k] = left_edge[height - 1 - k] * enumeration.finv(k);
          }
          for (int j = 0; j < width; j++) {
            Mint sum = 0;
            for (int k = 0; k < height; k++) {
              sum += scaled[k] * enumeration.fact(j + k);
            }
            top_edge[j] += sum * enumeration.finv(j);
          }
        }
        if (has_bottom) {
          vector<Mint> scaled(width);
          for (int k = 0; k < width; k++) {
            scaled[k] = bottom_edge[width - 1 - k] * enumeration.finv(k);
          }
          for (int j = 0; j < height; j++) {
            Mint sum = 0;
            for (int k = 0; k < width; k++) {
              sum += scaled[k] * enumeration.fact(j + k);
            }
            right_edge[j] += sum * enumeration.finv(j);
          }
        }
      } else {
        int size = 1;
        while (size < height + width - 1) size <<= 1;

        vector<Mint> kernel(size);
        for (int i = 0; i < height + width - 1; i++) {
          kernel[i] = enumeration.fact(i);
        }
        NTT::ntt(kernel);

        // Fold the inverse-transform normalization into the shared kernel.
        const Mint inv_size = Mint(1) / Mint(size);
        for (auto& x : kernel) x *= inv_size;

        auto apply_middle_product = [&](const vector<Mint>& input,
                                        vector<Mint>& output) {
          const int input_size = static_cast<int>(input.size());
          vector<Mint> f(size);
          f[0] = input[input_size - 1];
          for (int k = 1; k < input_size; k++) {
            f[size - k] = input[input_size - 1 - k] * enumeration.finv(k);
          }
          NTT::ntt(f);
          for (int i = 0; i < size; i++) f[i] *= kernel[i];
          NTT::intt(f, false);
          for (int i = 0; i < static_cast<int>(output.size()); i++) {
            output[i] += f[i] * enumeration.finv(i);
          }
        };

        if (has_left) apply_middle_product(left_edge, top_edge);
        if (has_bottom) apply_middle_product(bottom_edge, right_edge);
      }
    }

    // Bottom -> top.
    if (has_bottom) {
      vector<Mint> kernel(width);
      for (int i = 0; i < width; i++) {
        kernel[i] = enumeration.fact(height - 1 + i) * enumeration.finv(i);
      }
      auto f = convolution_prefix(bottom_edge, std::move(kernel), width);
      const Mint coefficient = enumeration.finv(height - 1);
      for (int i = 0; i < width; i++) top_edge[i] += coefficient * f[i];
    }

    // Left -> right.
    if (has_left) {
      vector<Mint> kernel(height);
      for (int i = 0; i < height; i++) {
        kernel[i] = enumeration.fact(width - 1 + i) * enumeration.finv(i);
      }
      auto f = convolution_prefix(left_edge, std::move(kernel), height);
      const Mint coefficient = enumeration.finv(width - 1);
      for (int i = 0; i < height; i++) right_edge[i] += coefficient * f[i];
    }

    return make_pair(top_edge, right_edge);
  };

  // Solve a one-sided staircase. `heights` must be nondecreasing, and
  // `start[i]` is an additive source at the i-th bottom-edge vertex.
  auto solve_one_sided = [&](const vector<int>& heights,
                             const vector<Mint>& start) -> vector<Mint> {
    const int size = static_cast<int>(heights.size());
    assert(size > 0);
    assert(static_cast<int>(start.size()) == size);

    vector<int> bounds(size);
    for (int i = 0; i < size; i++) {
      assert(heights[i] >= 0);
      if (i > 0) assert(heights[i - 1] <= heights[i]);
      bounds[i] = heights[i] + 1;
    }

    auto rec = [&](auto& self, int l, int r, int bottom,
                   const vector<Mint>& bottom_edge) -> vector<Mint> {
      assert(static_cast<int>(bottom_edge.size()) == r - l);
      if (l + 1 == r) {
        return vector<Mint>(bounds[l] - bottom, bottom_edge[0]);
      }

      const int mid = (l + r) >> 1;
      const int height = bounds[mid] - bottom;

      auto left_edge = self(
          self, l, mid, bottom,
          vector<Mint>(bottom_edge.begin(), bottom_edge.begin() + mid - l));
      left_edge.resize(height);

      auto [top_edge, right_edge] = propagate_rectangle(
          left_edge,
          vector<Mint>(bottom_edge.begin() + mid - l, bottom_edge.end()));
      right_edge.resize(bounds[r - 1] - bottom);

      auto upper_right = self(self, mid, r, bounds[mid], top_edge);
      for (int i = 0; i < static_cast<int>(upper_right.size()); i++) {
        right_edge[height + i] += upper_right[i];
      }
      return right_edge;
    };

    return rec(rec, 0, size, 0, start);
  };

  // Decompose the corridor into alternating horizontal and vertical
  // one-sided staircases. Vertical pieces are transposed.
  const int distance = static_cast<int>(
      upper_bound(lower_boundary.begin(), lower_boundary.end(), 0) -
      lower_boundary.begin());
  int px = 0, py = 0;
  int qx = distance - 1, qy = 0;
  if (qx == 0) qy = upper_boundary[0];

  vector<Mint> current(abs(qx - px) + abs(qy - py) + 1);
  current[0] = Mint(1);
  bool first_piece = true;

  while (qx != n - 1 || qy != upper_boundary[n - 1]) {
    // Boundary DP values are prefix sums of additive sources.
    if (!first_piece) {
      for (int i = static_cast<int>(current.size()) - 1; i >= 1; i--) {
        current[i] -= current[i - 1];
      }
    }
    first_piece = false;

    if (py == qy) {
      vector<int> heights(qx - px + 1);
      for (int i = 0; i <= qx - px; i++) {
        heights[i] = upper_boundary[px + i] - py;
      }
      current = solve_one_sided(heights, std::move(current));
      px = qx;
      py = qy;
      qy = upper_boundary[qx];
    } else {
      // qx + 1 is the first lower-boundary index above py. The pointer moves
      // monotonically over this vertical segment.
      int x = qx + 1;
      const int base_x = x;
      vector<int> heights(qy - py + 1);
      for (int i = 0; i <= qy - py; i++) {
        const int y = py + i;
        while (x < n && lower_boundary[x] <= y) ++x;
        heights[i] = x - base_x;
      }
      current = solve_one_sided(heights, std::move(current));
      px = qx;
      py = qy;
      qx = x - 1;
    }
  }

  return current.back();
}
#line 2 "math/combinatorics/montgomery-mod-int.hpp"

template <uint32_t mod_, bool fast = false>
struct MontgomeryModInt {
 private:
  using mint = MontgomeryModInt;
  using i32 = int32_t;
  using i64 = int64_t;
  using u32 = uint32_t;
  using u64 = uint64_t;

  static constexpr u32 get_r() {
    u32 ret = mod_;
    for (i32 i = 0; i < 4; i++) ret *= 2 - mod_ * ret;
    return ret;
  }

  static constexpr u32 r = get_r();

  static constexpr u32 n2 = -u64(mod_) % mod_;

  static_assert(r * mod_ == 1, "invalid, r * mod != 1");
  static_assert(mod_ < (1 << 30), "invalid, mod >= 2 ^ 30");
  static_assert((mod_ & 1) == 1, "invalid, mod % 2 == 0");

  u32 x;

 public:
  MontgomeryModInt() : x{} {}

  MontgomeryModInt(const i64& a)
      : x(reduce(u64(fast ? a : (a % mod() + mod())) * n2)) {}

  static constexpr u32 reduce(const u64& b) {
    return u32(b >> 32) + mod() - u32((u64(u32(b) * r) * mod()) >> 32);
  }

  mint& operator+=(const mint& p) {
    if (i32(x += p.x - 2 * mod()) < 0) x += 2 * mod();
    return *this;
  }

  mint& operator-=(const mint& p) {
    if (i32(x -= p.x) < 0) x += 2 * mod();
    return *this;
  }

  mint& operator*=(const mint& p) {
    x = reduce(u64(x) * p.x);
    return *this;
  }

  mint& operator/=(const mint& p) {
    *this *= p.inv();
    return *this;
  }

  mint operator-() const { return mint() - *this; }

  mint operator+(const mint& p) const { return mint(*this) += p; }

  mint operator-(const mint& p) const { return mint(*this) -= p; }

  mint operator*(const mint& p) const { return mint(*this) *= p; }

  mint operator/(const mint& p) const { return mint(*this) /= p; }

  bool operator==(const mint& p) const {
    return (x >= mod() ? x - mod() : x) == (p.x >= mod() ? p.x - mod() : p.x);
  }

  bool operator!=(const mint& p) const {
    return (x >= mod() ? x - mod() : x) != (p.x >= mod() ? p.x - mod() : p.x);
  }

  u32 val() const {
    u32 ret = reduce(x);
    return ret >= mod() ? ret - mod() : ret;
  }

  mint pow(u64 n) const {
    mint ret(1), mul(*this);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  mint inv() const { return pow(mod() - 2); }

  friend ostream& operator<<(ostream& os, const mint& p) {
    return os << p.val();
  }

  friend istream& operator>>(istream& is, mint& a) {
    i64 t;
    is >> t;
    a = mint(t);
    return is;
  }

  static constexpr u32 mod() { return mod_; }
};

template <uint32_t mod>
using modint = MontgomeryModInt<mod>;
using modint998244353 = modint<998244353>;
using modint1000000007 = modint<1000000007>;
#line 1 "other/scanner.hpp"
/**
 * @brief Scanner(高速入力)
 */
struct Scanner {
 public:
  explicit Scanner(FILE* fp) : fp(fp) {}

  template <typename T, typename... E>
  void read(T& t, E&... e) {
    read_single(t);
    read(e...);
  }

 private:
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  FILE* fp = nullptr;
  char* st = line;
  char* ed = line;

  void read() {}

  static inline bool is_space(char c) { return c <= ' '; }

  void reread() {
    ptrdiff_t len = ed - st;
    memmove(line, st, len);
    char* tmp = line + len;
    ed = tmp + fread(tmp, 1, line_size - len, fp);
    *ed = 0;
    st = line;
  }

  void skip_space() {
    while (true) {
      if (st == ed) reread();
      while (*st && is_space(*st)) ++st;
      if (st != ed) return;
    }
  }

  template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
  void read_single(T& s) {
    skip_space();
    if (st + int_digits >= ed) reread();
    bool neg = false;
    if (is_signed<T>::value && *st == '-') {
      neg = true;
      ++st;
    }
    typename make_unsigned<T>::type y = *st++ - '0';
    while (*st >= '0') {
      y = 10 * y + *st++ - '0';
    }
    s = (neg ? -y : y);
  }

  template <typename T, enable_if_t<is_same<T, string>::value, int> = 0>
  void read_single(T& s) {
    s = "";
    skip_space();
    while (true) {
      char* base = st;
      while (*st && !is_space(*st)) ++st;
      s += string(base, st);
      if (st != ed) return;
      reread();
    }
  }

  template <typename T>
  void read_single(vector<T>& s) {
    for (auto& d : s) read(d);
  }
};
#line 8 "test/verify/yosupo-number-of-increasing-sequences-between-two-sequences.test.cpp"

using mint = modint998244353;

int main() {
  Scanner input(stdin);
  int N, M;
  input.read(N, M);
  vector< int > A(N), B(N);
  input.read(A, B);
  cout << count_bounded_increasing_sequences< mint >(A, B).val() << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	3 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	example_02	AC	2 ms	4 MB
g++	maxi_00	AC	6 ms	5 MB
g++	maxi_01	AC	852 ms	12 MB
g++	maxi_02	AC	843 ms	12 MB
g++	maxi_03	AC	6 ms	5 MB
g++	maxi_04	AC	848 ms	12 MB
g++	random_00	AC	5 ms	5 MB
g++	random_01	AC	218 ms	7 MB
g++	random_02	AC	529 ms	8 MB
g++	special_00	AC	766 ms	15 MB
g++	special_01	AC	676 ms	14 MB
g++	special_02	AC	632 ms	16 MB
g++	special_03	AC	821 ms	15 MB
g++	special_04	AC	637 ms	14 MB
g++	special_05	AC	798 ms	17 MB
clang++	example_00	AC	3 ms	4 MB
clang++	example_01	AC	2 ms	4 MB
clang++	example_02	AC	2 ms	4 MB
clang++	maxi_00	AC	6 ms	5 MB
clang++	maxi_01	AC	881 ms	12 MB
clang++	maxi_02	AC	876 ms	11 MB
clang++	maxi_03	AC	6 ms	5 MB
clang++	maxi_04	AC	881 ms	12 MB
clang++	random_00	AC	6 ms	5 MB
clang++	random_01	AC	222 ms	7 MB
clang++	random_02	AC	551 ms	8 MB
clang++	special_00	AC	799 ms	15 MB
clang++	special_01	AC	704 ms	14 MB
clang++	special_02	AC	668 ms	16 MB
clang++	special_03	AC	864 ms	14 MB
clang++	special_04	AC	655 ms	14 MB
clang++	special_05	AC	861 ms	17 MB

Back to top page