C++ vectorクラスで二次元配列 & Combination の計算

C++には動的な配列を作成できるクラス、vectorが備わっており、これを用いれば可変長の配列が作れて便利。
詳細は
C++ 動的配列クラス std::vector 入門

などによくまとまっている。
今回はこれを使ってCombinationの計算などをしてみようといった趣向
Combinationのけいさんはよく知られている
{ \displaystyle \begin{eqnarray} {}_nC_k =\frac{n!}{(n-k)!k!} \end{eqnarray} }
でやるとn!がでかすぎて、桁あふれを起こしてしまう
(intの大きさの最大は2,147,483,647なので13!ぐらいで余裕であふれてしまう。)
そこでお手軽にある程度の大きさのCombinationを計算するのに用いられるのが以下の式である
{ \displaystyle \begin{eqnarray} {}_nC_k ={}_{n-1}C_{k-1}+{}_{n-1}C_{k} \end{eqnarray} }
いわゆるパスカルの三角形を利用した式である。
算数的に解釈するならばn人からk人を選ぶ方法と、n人からある一人を除いてその人を必ず選び残りのn-1人からk-1人を選ぶ組み合わせ（{ \displaystyle{}_{n-1}C_{k-1}}））にn人からある一人を除いてそれを必ず選ばないでｋ人選ぶ組み合わせ（{ \displaystyle{}_{n-1}C_k}）を足したものは等しいといった内容である。

#include<iostream>
#include<vector>
using namespace std;
void comb(vector<vector <long long int> > &v){
  for(int i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(int k = 1;k <v.size();k++){
    for(int j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

int main(){
  int N,K;
  cin >> N >>K;
  vector<vector<long long int> > v(N+1,vector<long long int>(N+1,0));
  comb(v);
  cout << v[N][K];
  return 0;
}

これで{ \displaystyle \begin{eqnarray} {}_NC_K \end{eqnarray} }が返ってくる。


二次元配列をどのように生成するかというと

  vector<vector<long long int> > v(N+1,vector<long long int>(N+1,0));

の部分で生成している。vectorの中にlong long int を要素とするvectorを入れているといったイメージ。
要するに

  vector<入れたい型> v(配列の個数(x),vector<入れたい型> (配列の個数,初期値));

などと書けばよい。

表記上の注意としては

vector<vector<long long int> >

の部分であるが

vector<vector<long long int>>

こう右端のスペースがない形で書いてしまうと一部のコンパイラでは怒られが発生する。

二次元配列を生成した後は適当にパスカルの三角形を上から計算していっている。
実際はパスカルの三角形には対称性があるので計算量は半分にできる。