Binomial Table(二項係数テーブル)
(math/combinatorics/binomial-table.hpp)

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+09:00
• Include: #include "math/combinatorics/binomial-table.hpp"

概要

二項係数テーブルをパスカルの三角形より求める.

• binomial_table(n): n 以下の二項係数テーブルを返す.

計算量

• $O(n^2)$

Code

/**
 * @brief Binomial Table(二項係数テーブル)
 * @docs docs/binomial-table.md
 */
template< typename T >
vector< vector< T > > binomial_table(int N) {
  vector< vector< T > > mat(N + 1, vector< T >(N + 1));
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= i; j++) {
      if(j == 0 || j == i) mat[i][j] = 1;
      else mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
    }
  }
  return mat;
}

#line 1 "math/combinatorics/binomial-table.hpp"
/**
 * @brief Binomial Table(二項係数テーブル)
 * @docs docs/binomial-table.md
 */
template< typename T >
vector< vector< T > > binomial_table(int N) {
  vector< vector< T > > mat(N + 1, vector< T >(N + 1));
  for(int i = 0; i <= N; i++) {
    for(int j = 0; j <= i; j++) {
      if(j == 0 || j == i) mat[i][j] = 1;
      else mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
    }
  }
  return mat;
}

Back to top page