Binomial Coefficient (Prime Mod)
(math/enumerative-combinatorics/BinomialCoefficientPrimeMod.hpp)

• View this file on GitHub
• Last update: 2026-04-13 13:43:31+09:00
• Include: #include "math/enumerative-combinatorics/BinomialCoefficientPrimeMod.hpp"

概要

素数 mod における二項係数を、階乗と階乗逆元の前計算により求める。

コンストラクタ

BinomialCoefficient(int n)

$[0, n]$ の階乗 fac と逆元階乗 inv を前計算する。前計算のテーブルがすでに存在する場合は、不足分を拡張する。

制約

• S は inv() を持つ型
• $0 \leq n$

計算量

• $O(n)$

nCr

S binom.nCr(int n, int r)

二項係数 $\binom{n}{r}$ を返す。$n < r$ のとき $0$ を返す。

制約

• $0 \leq n$
• $0 \leq r$
• n は前計算したテーブルの範囲内

計算量

• $O(1)$

Verified with

• verify/LibraryChecker/math/enumerative-combinatorics/BinomialCoefficientPrimeMod.test.cpp

Code

template <class S>
struct BinomialCoefficient {
 private:
  inline static vector<S> fac, inv;

 public:
  BinomialCoefficient(int n) {
    int p = int(fac.size());
    if (p <= n) {
      fac.resize(n + 1);
      inv.resize(n + 1);
      if (p == 0) fac[0] = 1;
      for (int i = p; i < n + 1; i++) {
        if (i == 0) continue;
        fac[i] = fac[i - 1] * i;
      }
      inv[n] = fac[n].inv();
      for (int i = n; i > p; i--) {
        if (i == 0) continue;
        inv[i - 1] = inv[i] * i;
      }
    }
  }

  S nCr(int n, int r) {
    if (n < r) return S(0);
    assert(fac.size() > n and fac.size() > r);
    return fac[n] * inv[r] * inv[n - r];
  }
};

#line 1 "math/enumerative-combinatorics/BinomialCoefficientPrimeMod.hpp"

template <class S>
struct BinomialCoefficient {
 private:
  inline static vector<S> fac, inv;

 public:
  BinomialCoefficient(int n) {
    int p = int(fac.size());
    if (p <= n) {
      fac.resize(n + 1);
      inv.resize(n + 1);
      if (p == 0) fac[0] = 1;
      for (int i = p; i < n + 1; i++) {
        if (i == 0) continue;
        fac[i] = fac[i - 1] * i;
      }
      inv[n] = fac[n].inv();
      for (int i = n; i > p; i--) {
        if (i == 0) continue;
        inv[i - 1] = inv[i] * i;
      }
    }
  }

  S nCr(int n, int r) {
    if (n < r) return S(0);
    assert(fac.size() > n and fac.size() > r);
    return fac[n] * inv[r] * inv[n - r];
  }
};

Back to top page