Luzhiled's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ei1333/library

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

概要

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

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

使い方

計算量

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

Code

/**
 * @brief Binomial(二項係数)
 * @docs docs/binomial.md
 */
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(二項係数)
 * @docs docs/binomial.md
 */
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