Binomial Table(二項係数テーブル) (math/combinatorics/binomial-table.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-table.hpp"

概要

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

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

計算量

• $O(n^2)$

Code

/**
 * @brief Binomial Table(二項係数テーブル)
 *
 */
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(二項係数テーブル)
 *
 */
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