lib/algorithm/offline_binomial_sum.hpp

• View this file on GitHub
• Last update: 2025-06-10 12:21:08+09:00
• Include: #include "lib/algorithm/offline_binomial_sum.hpp"

Depends on

• Mo's algorithm (lib/algorithm/mo.hpp)
• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• 二項係数 (lib/math/combination.hpp)
• lib/math/modint.hpp

Verified with

• test/yukicoder/2206.test.cpp

Code

#pragma once
#include <concepts>
#include <vector>
#include "algorithm/mo.hpp"
#include "math/combination.hpp"
#include "math/modint.hpp"

template <class mint = modint998>
requires(std::derived_from<mint, internal::modint_base>)
std::vector<mint> offline_binomial_sum(const std::vector<std::pair<int, int>> &queries) {
    std::vector<mint> res(queries.size());
    if (queries.empty()) return res;
    int max_n = queries[0].first;
    for (int i = 1; i < (int)queries.size(); ++i) max_n = std::max(max_n, queries[i].first);
    Mo mo(max_n + 1);
    for (int i = 0; i < (int)queries.size(); ++i) mo.add(queries[i].second, queries[i].first);
    Combination<mint> binom;
    mint sum = 1;
    mint inv2 = mint(2).inv();
    int n = 0, k = 0;
    auto al = [&binom, &sum, &n, &k](int) { sum -= binom(n, k--); };
    auto dl = [&binom, &sum, &n, &k](int) { sum += binom(n, ++k); };
    auto ar = [&binom, &sum, &n, &k](int) { sum += sum - binom(n++, k); };
    auto dr = [&binom, &sum, &n, &k, &inv2](int) { sum = (sum + binom(--n, k)) * inv2; };
    auto rem = [&res, &sum](int x) { res[x] = sum; };
    mo.solve(al, ar, dl, dr, rem);
    return res;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: algorithm/mo.hpp: line -1: no such header

Back to top page