nCrを求めたい。

ナイーブな実装では、オーバーフローする。
いい感じにするといい感じ。
パスカルの三角形を使うともっと良い感じ。

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

//ナイーブな実装
ll combi1(int n,int r){
    if(n < r) return 0;
    ll ret = 1;
    for(int i=0;i<r;i++){
        ret *= n-i;
    }
    for(int i=r;i>=1;i--){
        ret /= i;
    }
    return ret;
}

//いい感じのやつ
ll combi2(int n,int r){
    if(n < r) return 0;
    ll ret = 1;
    for(int i=0;i<r;i++){
        ret *= n-i;
        ret /= i+1;
    }
    return ret;
}

ll combi3(int n,int r){
    int N = n+1;
    vector<vector<ll> > memo(N,vector<ll>(N,0));
    memo[0][0] = 1;
    for(int i=1;i<N;i++){
        memo[i][0] = memo[i-1][0];
        for(int j=1;j<N;j++){
            memo[i][j] = memo[i-1][j-1] + memo[i-1][j];
        }
    }
    return memo[n][r];
}

int main(){
    int k = 66;
    for(int i=1;i<=k;i++){
        cout << combi1(k,i) << " " << combi2(k,i) << " " << combi3(k,i) << endl;
    }
}

いい感じのは、n=61まで大丈夫だった。パスカルの三角形は、n=66くらいまで大丈夫っぽい。
ちなみに、小数出そうだけど、連続するa個の整数には必ず、aの倍数が含まれているから大丈夫。

参照:
動的計画法とは (ドウテキケイカクホウとは) [単語記事] - ニコニコ大百科