Binomial Coefficient Prefix Sum Query (math/combinatorics/binomial-prefix-sum-query.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2026-07-17 15:50:59+00:00
Include: #include "math/combinatorics/binomial-prefix-sum-query.hpp"

パスカルの三角形上を移動しながら、二項係数の Prefix Sum を求めます。問い合わせ位置が近い場合に有効です。

コンストラクタ

BinomialPrefixSumQuery<Mint>(int max_n)

クエリで与える $n$ の最大値を max_n で初期化します。初期位置は $(n,k)=(0,-1)$ で、保持する値は $0$ です。

制約

$0 \leq$ max_n $\lt$ Mint::mod()
Mint では $2$ の逆元を計算できる

計算量

max_n を $N$、Mint::mod() を $p$ とすると、

時間計算量: $O(N+\log p)$

reset

void reset()

位置を $(n,k)=(0,-1)$、保持する値を $0$ に戻します。二項係数の前計算は保持します。

計算量

$O(1)$

move

Mint move(int n, int k)

位置を $(n,k)$ へ移動し、

\[\sum_{i=0}^{k}\binom{n}{i}\]

を返します。$k=-1$ の場合は $0$ を返します。

制約

$0 \leq n \leq$ max_n
$-1 \leq k \leq n$

計算量

移動前の位置を $(n_0,k_0)$ とすると、

\[O\left(\lvert n-n_0\rvert+\lvert k-k_0-(n-n_0)\rvert\right)\]

です。

value

Mint value() const

現在位置の二項係数の Prefix Sum を返します。

計算量

$O(1)$

Depends on

Enumeration (組み合わせ) (math/combinatorics/enumeration.hpp)

Verified with

test/unittest/binomial-prefix-sum-query.test.cpp

Code

#pragma once

#include "enumeration.hpp"

/**
 * @brief Binomial Coefficient Prefix Sum Query
 */
template <typename Mint>
struct BinomialPrefixSumQuery {
 private:
  static int check_max_n(int max_n) {
    assert(max_n >= 0);
    return max_n;
  }

  int max_n_, n_ = 0, k_ = -1;
  Mint sum_ = 0, inv_two_;
  Enumeration<Mint> binom_;

 public:
  explicit BinomialPrefixSumQuery(int max_n)
      : max_n_(check_max_n(max_n)),
        inv_two_(Mint(1) / Mint(2)),
        binom_(max_n_) {}

  void reset() {
    n_ = 0;
    k_ = -1;
    sum_ = 0;
  }

  Mint move(int n, int k) {
    assert(0 <= n && n <= max_n_);
    assert(-1 <= k && k <= n);
    while (n_ < n) {
      sum_ += sum_ + binom_.C(n_, k_ + 1);
      ++n_;
      ++k_;
    }
    while (n_ > n) {
      --n_;
      --k_;
      sum_ = (sum_ - binom_.C(n_, k_ + 1)) * inv_two_;
    }
    while (k_ < k) {
      sum_ += binom_.C(n_, k_ + 1);
      ++k_;
    }
    while (k_ > k) {
      --k_;
      sum_ -= binom_.C(n_, k_ + 1);
    }
    return sum_;
  }

  Mint value() const { return sum_; }
};

#line 2 "math/combinatorics/binomial-prefix-sum-query.hpp"

#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 4 "math/combinatorics/binomial-prefix-sum-query.hpp"

/**
 * @brief Binomial Coefficient Prefix Sum Query
 */
template <typename Mint>
struct BinomialPrefixSumQuery {
 private:
  static int check_max_n(int max_n) {
    assert(max_n >= 0);
    return max_n;
  }

  int max_n_, n_ = 0, k_ = -1;
  Mint sum_ = 0, inv_two_;
  Enumeration<Mint> binom_;

 public:
  explicit BinomialPrefixSumQuery(int max_n)
      : max_n_(check_max_n(max_n)),
        inv_two_(Mint(1) / Mint(2)),
        binom_(max_n_) {}

  void reset() {
    n_ = 0;
    k_ = -1;
    sum_ = 0;
  }

  Mint move(int n, int k) {
    assert(0 <= n && n <= max_n_);
    assert(-1 <= k && k <= n);
    while (n_ < n) {
      sum_ += sum_ + binom_.C(n_, k_ + 1);
      ++n_;
      ++k_;
    }
    while (n_ > n) {
      --n_;
      --k_;
      sum_ = (sum_ - binom_.C(n_, k_ + 1)) * inv_two_;
    }
    while (k_ < k) {
      sum_ += binom_.C(n_, k_ + 1);
      ++k_;
    }
    while (k_ > k) {
      --k_;
      sum_ -= binom_.C(n_, k_ + 1);
    }
    return sum_;
  }

  Mint value() const { return sum_; }
};