1401. A Thousand Binomials From One Table

Answer q queries, each asking for C(n, k) modulo a prime p. Print 0 when k is greater than n.

You are guaranteed that every n is smaller than p.

q = 4, p = 1000000007 5 2 -> 10 5 0 -> 1 5 5 -> 1 5 6 -> 0 since k > n

## What most people try first

Answer each query on its own, as problem 1326 does: build the three factorials it needs and take one modular inverse by Fermat's little theorem. That is O(n + log p) per query, so with q at 1000 and n at 10^6 it is 10^9 multiplications plus a thousand modular powers. The factorials are the same every time, which is the waste.

## One table, and exactly one modular power

Build f[i] = i! mod p for i up to the largest n in the input. The inverse factorials look like they need a modular power each, but they satisfy a recurrence running downward:

f[i] = f[i-1] * i so 1/f[i-1] = (1/f[i]) * i

So invert the single largest factorial with one Fermat power and walk down:

g[nmax] = f[nmax]^(p-2) mod p for i = nmax down to 1: g[i-1] = g[i] * i mod p

Then every query is three table lookups and two multiplications:

C(n, k) = f[n] * g[k] * g[n-k] mod p

## Why it is correct

Fermat's little theorem says x^(p-1) = 1 mod p whenever p is prime and x is not a multiple of p, so x^(p-2) is the inverse of x. The guarantee n < p is what makes every factorial up to nmax free of the factor p, so none of them is 0 modulo p and every inverse exists. That guarantee is not decoration: if n could reach p, then n! would be 0 modulo p and this whole method would collapse, which is the case problem 1402 handles with Lucas' theorem instead.

The downward recurrence is correct because it is the original recurrence read backwards: multiplying both sides of f[i] = f[i-1] * i by 1/(f[i-1] * f[i]) gives 1/f[i-1] = i / f[i].

## Overflow

p reaches 1000000009, so f[i-1] * i and f[n] * g[k] are products of two values near 10^9, which is near 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, and does not fit a signed 32-bit one, whose limit is 2147483647: a 32-bit build answers 679072881 where the truth is 996692777. In JavaScript 10^18 is past 2^53, so a plain a * b is wrong; the references split a at 65536 so that every intermediate stays below 2^53, which is exact and avoids two million BigInt allocations.

## Cost

O(nmax + log p) once, then O(1) per query.

Constraints - `1 ≤ q ≤ 1000` - `0 ≤ n ≤ 1000000` - `0 ≤ k ≤ 1000000` - `1000003 ≤ p ≤ 1000000009`, `p` is prime, and `n < p`