組み合わせを高速に計算する

# ${}_n \mathrm{C} _r$の定義

異なる$n$個のものから$r$個を選ぶ組み合わせの総数．

# いろんな実装

再帰的に計算する

1
2
3
4
5
6
long long combination(long long n, long long r) {
    if (n == r || r == 0)
        return 1;
    else
        return combination(n - 1, r - 1) + combination(n - 1, r);
}

パスカルの三角形を用いる
- 二次元配列の下半分をパスカルの三角形のルールに従って埋めていく
- 小さいところから埋まっていくので直接定義式どおりに計算したときにオーバーフローするような大きい組み合わせを計算できる．
  - ABC185-Cはこれを使って AC

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
vector<vector<long long>> combination(long long n, long long r) {
    vector<vector<long long>> table(n+1, vector<long long>(n+1, 0));
    for (int i = 0; i < table.size(); i++) {
        table[i][0] = 1;
        table[i][i] = 1;
    }

    for (int j = 1; j < table.size(); j++) {
        for (int k = 1; k < j; k++) {
            table[j][k] = table[j - 1][k - 1] + table[j - 1][k]; // 真上と左上の和
        }
    }

    return table; // table[n][r]がnCrの値
}