Refactoring: Precomputing Factorials

C++

const int MAXN = 200000;
const long long MOD = 1e9 + 7;

long long fact[MAXN + 1], inv_fact[MAXN + 1];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++)
        fact[i] = fact[i - 1] * i % MOD;

    inv_fact[MAXN] = mod_pow(fact[MAXN], MOD - 2, MOD);
    for (int i = MAXN; i >= 1; i--)
        inv_fact[i - 1] = inv_fact[i] * i % MOD;
}

long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD
           * inv_fact[n - r] % MOD;
}

Compute inv_fact by descending: (i−1)!⁻¹ = i!⁻¹ × i mod M.

Rust

const MAXN: usize = 200_000;
const MOD: u64 = 1_000_000_007;

struct Combinatorics {
    fact: Vec<u64>,
    inv_fact: Vec<u64>,
}

impl Combinatorics {
    fn new() -> Self {
        let mut fact = vec![1; MAXN + 1];
        for i in 1..=MAXN {
            fact[i] = fact[i - 1] * i as u64 % MOD;
        }

        let mut inv_fact = vec![1; MAXN + 1];
        inv_fact[MAXN] = mod_pow(fact[MAXN], MOD - 2, MOD);
        for i in (1..=MAXN).rev() {
            inv_fact[i - 1] = inv_fact[i] * i as u64 % MOD;
        }

        Combinatorics { fact, inv_fact }
    }

    fn ncr(&self, n: usize, r: usize) -> u64 {
        if r > n { return 0; }
        self.fact[n] * self.inv_fact[r] % MOD
            * self.inv_fact[n - r] % MOD
    }
}