二項係数テーブル(Binomial-Table)

説明

二項係数テーブルを求める。

計算量

• $O(N^2)$

実装例

• binomial_table($n$):= $n$ 以下の二項係数テーブルを求める。

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;
}