Binomial(二項係数) (math/combinatorics/binomial.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "math/combinatorics/binomial.hpp"

概要

二項係数 ${}_n \mathrm{C} _k$ を $\displaystyle \frac {k(k-1)\dots (n-k+1)} {k(k-1)\dots 1}$ を利用して求める.

$k$ が小さい時に有効.

使い方

• binomial(N, K): ${}_n \mathrm{C} _k$ を返す.

計算量

• $O(K \log K)$

ただし逆元が $O(1)$ で求まる場合 $O(K)$

Code

/**
 * @brief Binomial(二項係数)
 *
 */
template <typename T>
T binomial(int64_t N, int64_t K) {
  if (K < 0 || N < K) return 0;
  static vector<T> invs;
  if (invs.size() < K + 1) {
    int pre_sz = max(1, (int)invs.size());
    invs.resize(K + 1);
    for (int i = pre_sz; i <= K; i++) {
      invs[i] = T(1) / i;
    }
  }
  T ret = 1;
  for (int64_t i = 1; i <= K; ++i) {
    ret *= N;
    N--;
    ret *= invs[i];
  }
  return ret;
}

#line 1 "math/combinatorics/binomial.hpp"
/**
 * @brief Binomial(二項係数)
 *
 */
template <typename T>
T binomial(int64_t N, int64_t K) {
  if (K < 0 || N < K) return 0;
  static vector<T> invs;
  if (invs.size() < K + 1) {
    int pre_sz = max(1, (int)invs.size());
    invs.resize(K + 1);
    for (int i = pre_sz; i <= K; i++) {
      invs[i] = T(1) / i;
    }
  }
  T ret = 1;
  for (int64_t i = 1; i <= K; ++i) {
    ret *= N;
    N--;
    ret *= invs[i];
  }
  return ret;
}

Back to top page