パスカルの三角形を利用して組み合わせの数を求める

ABC 132 D 問題 の公式解説で、パスカルの三角形を利用して組み合わせの数を求めていたが、一見して何をしているか理解できなかった。

実装はこんな感じで、nCk を計算できる。

  int n, k;
  cin >> n >> k;
  int c[105][105] = {};
  c[0][0] = 1;
  for(int i=0; i<=100; i++) {
    for(int j=0; j<=i; j++) {
      c[i+1][j] += c[i][j];
      c[i+1][j+1] += c[i][j];
    }
  }
  cout << c[n][k] << endl;

パスカルの三角形とは何か、パスカルの三角形がなぜ組み合わせの数と対応するのかはこちらを参照して頂くとして、自分が分からなかったのはこの実装でパスカルの三角形が求められる理由。

これは図で書いてみると分かりやすくて、c[i][j] を下段の c[i+1][j], c[i+1][j+1] に配っているイメージ。

○
| \
○  ○
| \ | \
○  ○  ○

これなら両端は必ず1になるし、両端以外はパスカルの三角形の定義通りの加算が行われた値になる。

ちなみに、組み合わせの数は公式を使って愚直に計算しても（数が大きくなければ）良いと思う。

  int n, k;
  cin >> n >> k;
  int ans = 1;
  for(int i=0; i<k; i++) {
    ans *= n-i;
  }
  ans /= k;
  cout << ans << endl;

ただし、組み合わせの数を求める度に O(k) の計算が必要になるのと、掛け算がオーバーフローする可能性もあるので、パスカルの三角形で事前に計算しておいた方が良い場合も多そう。