Template: Modular arithmetic library

Exercise

Build a small, reusable modular arithmetic toolkit for competitive programming. Contract:

• mod_pow(base, exp, m) — base^exp mod m via binary exponentiation.
• mod_inv(a, m) — multiplicative inverse of a modulo a prime m, via Fermat's little theorem.
• Combo::new(n, m) / Combo::ncr(n, k) — preallocate factorial and inverse-factorial tables up to n; return nCr mod m in O(1).

Target: a header-file-style library you drop into every contest and forget about. No dynamic dispatch, no allocation on the hot path, no panics on standard inputs.

Intuition

Three ideas:

1. Binary exponentiation. base^exp computed in O(log exp) by halving the exponent. Every multiplication is done mod m to prevent overflow.
2. Fermat's little theorem. For prime m and gcd(a, m) = 1, a^(m-1) ≡ 1 mod m, so a^(m-2) ≡ a^(-1) mod m. This gives mod_inv in O(log m).
3. Factorial caching. For many nCr queries with fixed m, precompute fact[0..=n] and inv_fact[0..=n]. Then nCr = fact[n] * inv_fact[k] * inv_fact[n-k] mod m is one multiplication triple.

The whole toolkit is ~30 lines and covers 90% of combinatorics contest problems.

Approach

pub fn mod_pow(mut base: u64, mut exp: u64, m: u64) -> u64 {
    if m == 1 { return 0; }
    base %= m;
    let mut acc: u64 = 1;
    while exp > 0 {
        if exp & 1 == 1 { acc = acc * base % m; }
        exp >>= 1;
        base = base * base % m;
    }
    acc
}

pub fn mod_inv(a: u64, m: u64) -> u64 {
    mod_pow(a, m - 2, m)
}

pub struct Combo {
    fact: Vec<u64>,
    inv_fact: Vec<u64>,
    m: u64,
}

impl Combo {
    pub fn new(n: usize, m: u64) -> Self {
        let mut fact = vec![1u64; n + 1];
        for i in 1..=n { fact[i] = fact[i - 1] * (i as u64) % m; }
        let mut inv_fact = vec![1u64; n + 1];
        inv_fact[n] = mod_inv(fact[n], m);
        for i in (1..=n).rev() {
            inv_fact[i - 1] = inv_fact[i] * (i as u64) % m;
        }
        Self { fact, inv_fact, m }
    }

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

// TS: use BigInt everywhere — (1e9 + 7) squared overflows Number.MAX_SAFE_INTEGER.
function modPow(base: bigint, exp: bigint, m: bigint): bigint {
  if (m === 1n) return 0n;
  let acc = 1n;
  let b = base % m;
  let e = exp;
  while (e > 0n) {
    if (e & 1n) acc = (acc * b) % m;
    e >>= 1n;
    b = (b * b) % m;
  }
  return acc;
}

function modInv(a: bigint, m: bigint): bigint {
  return modPow(a, m - 2n, m);
}

class Combo {
  private fact: bigint[];
  private invFact: bigint[];
  constructor(n: number, private m: bigint) {
    this.fact = new Array(n + 1).fill(1n);
    for (let i = 1; i <= n; i++) this.fact[i] = (this.fact[i - 1] * BigInt(i)) % m;
    this.invFact = new Array(n + 1).fill(1n);
    this.invFact[n] = modInv(this.fact[n], m);
    for (let i = n; i >= 1; i--) this.invFact[i - 1] = (this.invFact[i] * BigInt(i)) % m;
  }
  ncr(n: number, k: number): bigint {
    if (k > n) return 0n;
    return ((this.fact[n] * this.invFact[k]) % this.m * this.invFact[n - k]) % this.m;
  }
}

Trace

mod_pow(3, 5, 100):

Result 43 — matches 243 mod 100.

Edge cases

• m = 1 — every residue is 0; handle before the loop.
• exp = 0 — return 1 immediately; the loop exits before multiplying, so the initial acc = 1 is correct.
• Non-prime m — mod_inv via Fermat is wrong. Use the extended Euclidean algorithm for composite m and general gcd(a, m) = 1.
• Overflow — all intermediates must be u64; (1e9 + 7)^2 ≈ 10^18 fits comfortably in u64::MAX ≈ 1.8 × 10^19. i64 also works but loses a bit for nothing.

Takeaway

Binary exponentiation, Fermat inverse, and factorial caches together are the 80/20 modular-arithmetic toolkit. They unlock every combinatorial DP — 62 (Unique Paths via C(m+n-2, m-1)), 1569, 1866, 2514 — and every number-theoretic contest problem that fits in a u64.

Keep this as a personal utility file and tune it once. Every subsequent contest or interview that asks for a big combinatorial answer is then a five-line problem.