Number of Increasing Sequences Between Two Sequences
(src/math/number_of_increasing_sequences_between_two_sequences.hpp)

• View this file on GitHub
• Last update: 2024-10-28 15:43:27+09:00
• Include: #include "src/math/number_of_increasing_sequences_between_two_sequences.hpp"

入力

長さ $n$ の数列 $a, b$

出力

任意の $i\ (0 \le i \lt n)$ について $a _ i \le x _ i \lt b _ i$ を満たす長さ $n$ の数列 $x$ の個数

計算量

$m := \max _ i b _ i - \min _ i a _ i$ として時間計算量 $\mathrm{O}((n + m) \log ^ 2 (n + m))$

Links

• 上限付き単調増加列の数え上げ - noshi91のメモ

出題例

• XXI Open Cup, Grand Prix of Tokyo J. Japanese Knowledge
• The 13th Chinese Northeast Collegiate Programming Contest I. Temperature Survey
• Good Bye 2022: 2023 is NEAR G. Koxia and Bracket
• Hokkaido University Competitive Programming Camp 2023 Day 1 L: 01 Swap
• AtCoder Grand Contest 058 B - Adjacent Chmax
• Codeforces Round 942 (Div. 1) E1. Again Counting Arrays (Easy Version)
• The 2nd Universal Cup. Stage 7: Two Capitals C. Cards
• AtCoder Beginner Contest 357 G - Stair-like Grid

Depends on

• Binomial Coefficients (src/math/binomial.hpp)

Verified with

• test/yosupo/number_of_increasing_sequences_between_two_sequences.test.cpp

Code

#pragma once
#include "../atcoder/convolution"
#include "math/binomial.hpp"

template <typename T> T number_of_increasing_sequences_between_two_sequences(std::vector<int> a, std::vector<int> b) {
    assert(a.size() == b.size());
    int n = a.size();
    for (int i = 0; i < n; i++) b[i]--;
    for (int i = 1; i < n; i++) a[i] = std::max(a[i], a[i - 1]);
    for (int i = n - 2; i >= 0; i--) b[i] = std::min(b[i], b[i + 1]);
    for (int i = 0; i < n; i++) {
        if (a[i] > b[i]) {
            return T(0);
        }
    }
    int m = b[n - 1] + 1;
    std::vector<int> L(n + m, 0), U(n + m, m - 1);
    U[0] = 0;
    L[n + m - 1] = m - 1;
    for (int i = 0; i < n; i++) {
        L[i + a[i]] = std::max(L[i + a[i]], a[i]);
        U[i + b[i] + 1] = std::min(U[i + b[i] + 1], b[i]);
    }
    n = L.size();
    for (int i = 1; i < n; i++) L[i] = std::max(L[i], L[i - 1]);
    for (int i = n - 2; i >= 0; i--) L[i] = std::max(L[i], L[i + 1] - 1);
    for (int i = n - 2; i >= 0; i--) U[i] = std::min(U[i], U[i + 1]);
    for (int i = 1; i < n; i++) U[i] = std::min(U[i], U[i - 1] + 1);
    Binomial<T> binom;

    auto extract = [](const std::vector<T>& dp, int l, int r = -1) {
        int len = dp.size();
        if (l >= len) return std::vector<T>();
        r = (r == -1 ? len : len < r ? len : r);
        return std::vector<T>(dp.begin() + l, dp.begin() + r);
    };
    auto go = [&](int l, int r, const std::vector<T>& dp) -> std::vector<T> {
        int len = r - l;
        std::vector<T> f(len + 1);
        for (int i = 0; i <= len; i++) f[i] = binom.C(len, i);
        return atcoder::convolution(dp, f);
    };
    auto dfs_only_L = [&](auto self, int l, int r, const std::vector<T>& dp) -> std::vector<T> {
        if (r - l == 1) {
            auto res = go(l, r, dp);
            if (L[l] != L[r]) res = extract(res, L[r] - L[l]);
            return res;
        }

        int m = (l + r) >> 1;
        auto M = go(l, m, extract(dp, L[m] - L[l]));
        auto buf = self(self, l, m, extract(dp, 0, L[m] - L[l]));
        while (M.size() < buf.size()) M.emplace_back(0);
        for (int i = 0; i < int(buf.size()); i++) M[i] += buf[i];

        auto R = go(m, r, extract(M, L[r] - L[m]));
        buf = self(self, m, r, extract(M, 0, L[r] - L[m]));
        while (R.size() < buf.size()) R.emplace_back(0);
        for (int i = 0; i < int(buf.size()); i++) R[i] += buf[i];
        return R;
    };
    auto dfs_only_R = [&](auto self, int l, int r, const std::vector<T>& dp) -> std::vector<T> {
        if (r - l == 1) {
            if (U[l] == U[r]) return std::vector<T>();
            return extract(go(l, r, dp), 1);
        }

        int m = (l + r) >> 1;
        std::vector<T> M((U[m] - U[l]) + (r - m), T(0));
        auto buf = go(l, m, dp);
        for (int i = m - l; i < std::min(int(buf.size()), r - l); i++) M[i - (m - l)] += buf[i];
        buf = self(self, l, m, extract(dp, int(dp.size()) - (m - l)));
        for (int i = 0; i < int(buf.size()); i++) M[i + (r - m)] += buf[i];

        std::vector<T> R(U[r] - U[l], T(0));
        buf = go(m, r, M);
        for (int i = r - m; i < std::min(int(buf.size()), ((U[m] - U[l]) + (r - m))); i++) R[i - (r - m)] += buf[i];
        buf = self(self, m, r, extract(M, int(M.size()) - (r - m)));
        for (int i = 0; i < int(buf.size()); i++) R[i + (U[m] - U[l])] += buf[i];
        return R;
    };
    auto dfs = [&](auto self, int l, int r, const std::vector<T>& dp) -> std::vector<T> {
        if (r - l == 1) {
            auto res = go(l, r, dp);
            return extract(res, L[r] - L[l], U[r] - L[l] + 1);
        }

        if (L[r] + (r - l) <= U[l]) {
            std::vector<T> res(U[r] - L[r] + 1, T(0));
            auto buf = go(l, r, extract(dp, L[r] - L[l]));
            for (int i = 0; i < std::min(int(buf.size()), U[l] - L[r] + 1); i++) res[i] += buf[i];
            buf = dfs_only_L(dfs_only_L, l, r, extract(dp, 0, L[r] - L[l]));
            for (int i = 0; i < int(buf.size()); i++) res[i] += buf[i];
            buf = dfs_only_R(dfs_only_R, l, r, extract(dp, int(dp.size()) - (r - l)));
            for (int i = 0; i < int(buf.size()); i++) res[int(res.size()) - 1 - i] += buf[int(buf.size()) - 1 - i];
            return res;
        }

        int m = (l + r) >> 1;
        return self(self, m, r, self(self, l, m, dp));
    };

    std::vector<T> init(1, T(1));
    auto last = dfs(dfs, 0, n - 1, init);
    return std::accumulate(last.begin(), last.end(), T(0));
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
    ~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/convolution.hpp: line -1: no such header

Back to top page