precomputing factorials and inverse factorials

Topics

• precomputation techniques
• combinatorics

Calculating binomial coefficient (nCr) efficiently often requires factorials and their modular multiplicative inverse. Precomputation comes handy when dealing with many queries.

The provided C++ code precomputes factorials and inverse factorials modulo a prime number (MOD).

1. modPow(a, b, mod): Calculates a^b % mod efficiently using binary exponentiation
2. precomputeFactorials():
   • fact[i] stores i! % MOD. It’s calculated iteratively: fact[i] = fact[i-1] * i % MOD
   • invFact[i] stores the modular inverse of i! → i.e., $i{!}^{-1}\mathrm{mod}\text{MOD}$
   • It uses fermat’s little theorem to calculate invFact[MAX] as fact[MAX]^(MOD-2) % MOD
   • invFact[i] is then calculated iteratively in reverse: invFact[i-1] = invFact[i] * i % MOD. This is because $\frac{1}{(i-1)!}=\frac{i}{i!}$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAX = 1e6; // adjust as necessary
 
ll fact[MAX+1], invFact[MAX+1];
 
// Modular exponentiation
ll modPow(ll a, ll b, ll mod) {
    ll res = 1LL % mod;
    a %= mod;
    while(b > 0) {
        if(b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
 
void precomputeFactorials() {
    fact[0] = 1;
    // O(n)
    for (int i = 1; i <= MAX; i++)
        fact[i] = (fact[i-1] * i) % MOD;
 
    invFact[MAX] = modPow(fact[MAX], MOD - 2, MOD);  // O(log MOD) Fermat's Little Theorem
 
    // O(n)
    for (int i = MAX; i >= 0; i--)
        invFact[i-1] = (invFact[i] * i) % MOD;
}

After calling precomputeFactorials(), you can calculate nCr % MOD as:

ll nCr = ((fact[n] * invFact[r]) % MOD * invFact[n-r]) % MOD;

T.C: Factorials → O(n), Inverse factorials → O(n + log MOD)
S.C: O(n)

Related