組み合わせ係数 nCr DP

概要

組み合わせ係数 $C(n,r)$ を求めます．$C(n,r) = C(n-1,r) + C(n-1,r-1)$ の漸化式に従ってメモ化再帰します．

計算量

初回は時間 $O(nr)$．空間 $O(nr)$．

実装

const ll mod = 1000000007;
const int MAX_N = 10000;  // 400MB
// const int MAX_N = 1024; // 4MB
// nCr % mod
ll nCr(int n, int r) {
    static bool done[MAX_N + 1][MAX_N / 2 + 2];
    static ll dp[MAX_N + 1][MAX_N / 2 + 2];  // 400MB
    if (n < 0 || r < 0 || n < r) return 0;
    if (r == 0) return 1;
    if (r > n - r) r = n - r;
    ll &res = dp[n][r];
    if (done[n][r]) return res;
    done[n][r] = true;
    return res = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % mod;
}