パスカルの三角形による二項係数(nCk)の計算

2020年3月23日2020年9月2日数学二項係数,動的計画法,パスカルの三角形

以下のような「上の2つを足して下の数字をつくる三角形」をパスカルの三角形といい、上から \(n\) 行目・左から \(k\) 個目の数は、\(_{n}\mathrm{C}_{k}\) に対応しています。(0-indexed)

これを利用することで、二項係数を求めることが可能です。上図から、
$$ {}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} $$
が成立していることが見て取れます。（例えば \({}_{5}\mathrm{C}_{3} = {}_{4}\mathrm{C}_{2}+{}_{4}\mathrm{C}_{3} \) です。）

アルゴリズム

※ 前処理での \({}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} \) は二項係数の有名公式ですし、パスカルの三角形の作り方からも分かります。

※ \({}_{i}\mathrm{C}_{j} = {}_{i-1}\mathrm{C}_{j-1}+{}_{i-1}\mathrm{C}_{j} \) は意味を考えると成立していることが分かります。左辺の意味は「\(i\) 個の中から \(j\) 個選ぶ」で、右辺の意味は「 あるものを1つ入れると決めた時は、残りの \(i-1\) の中から \(j-1\) 個選ぶ。入れないと決めた時は、残りの \(i-1\) の中から \(j\) 個選ぶ」ということを表しています。左辺と右辺は同じ場合の数です。

※ 二項係数は n が大きく k が n/2 に近い時に非常に大きな値になります。固定長の整数型では容易にオーバーフローしてしまう可能性があるので注意してください。（具体的には、\(_{50}\mathrm{C}_{25}\) は約 \(10^{14}\) ほどになり、32bit の整数型では収まりません。64bit 必要になります。）

※ 競技プログラミングなどでは、二項係数を素数で割った余りを求めさせる問題が多いです。求め方はこちらを参照してください。

計算量

• 前処理：\(O(n^2)\)
• クエリ：\(O(1)\)

C++ での実装例

標準入力から n と k を受け取って、nCk を返すプログラムです。

#include <bits/stdc++.h>
using namespace std;

/*
    前処理: O(MAX_N*MAX_N)
    nCk(n,k): nCk の計算。O(1)
*/
const int MAX_N = 50;         // n の最大値
vector<vector<long long>> com;  // 前計算の結果を保存

// 動的計画法で前処理
void init() {
    com.assign(MAX_N, vector<long long>(MAX_N));
    com[0][0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        com[i][0] = 1;
        for (int j = 1; j < MAX_N; j++) {
            com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]);
        }
    }
}
// nCk を取得
long long nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return com[n][k];
}

int main() {
    long long n, k;
    cin >> n >> k;
    init();
    cout << nCk(n, k) << endl;
}