パスカルの三角形とnCr

const int N_MAX = 1001;
ll pascal[N_MAX][N_MAX] = {};

void calc_pascal(){
    FOR(i, 0, N_MAX){
        pascal[i][0] = 1;
    }
    pascal[1][1] = 1;

    FOR(i, 2, N_MAX){
        for(int j=1; j<=i; j++){
            pascal[i][j] = pascal[i-1][j] + pascal[i-1][j-1];
        }
    }
}

ll nCr(ll n, ll r){
    return pascal[n][r];
}

• パスカルの三角形を求めることは、nCrの事前計算となる
• N=1000程度ならこれでいい
  • 本当？1000_C_500 = 10³⁰くらい
  • long doubleで収まるかギリギリ

使った問題

• Problem - C - Codeforces https://codeforces.com/contest/131/problem/C
  • AC https://codeforces.com/contest/131/submission/74606920

パスカル 数学論文集 (ちくま学芸文庫)