SyntaxPilot
Courses/Competitive Programming/Lesson 23

Competitive Programming · Lesson 23 of 90 · 15 min

Combinatorics: nCr mod p with factorials

queued

These are the notes for Competitive Programming episode 23 (combinatorics). We count choices from zero, invent the formula C(n, r) = n! / (r! · (n−r)!), and meet an original problem, Squad Picks, with up to 10^5 questions and n up to 10^6, answers mod 10^9 + 7. Factorials in long long overflow at 21!, Pascal's triangle avoids division but needs a 4 TB table, and two precomputed "fare charts", factorials and inverse factorials mod p, answer every query in O(1). A stress test checks the fast formula against Pascal on 501501 pairs. Then two applications: grid paths (Rider Routes) and stars and bars (laddoos among kids), and three real bugs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

Before this episode: episode 21 (modular arithmetic and fast power) and episode 22 (modular inverse with Fermat's little theorem).

The real-life hooks

Picking openers. A cricket coach has five players, A to E, and needs two openers. A with B is the same pair as B with A, so order doesn't matter. Listing them gives 10 pairs.

The captain's question. To count pairs from A–E, look at one player, E. Either E plays (pick 1 more from A–D: 4 ways) or E sits out (pick 2 from A–D: 6 ways). Every pair is in exactly one case: 4 + 6 = 10. That is Pascal's rule.

The railway fare chart. A booking clerk doesn't calculate each fare at the window: the fare chart is printed once, and every query is a lookup. We print two charts, f[i] = i! mod p and inv[i] = 1 / i! mod p, and every C(n, r) is three lookups multiplied.

The delivery rider. A rider must go a blocks east and b blocks north through a city grid, never going back. Every shortest route is a string of a E's and b N's.

Laddoos for kids. Share 10 identical laddoos among 4 kids (a kid may get none): line up the laddoos as stars and drop 3 bars between them.

Counting choices from zero

  • A combination is a choice of r items out of n where order doesn't matter. The number of combinations is written C(n, r), said "n choose r" (also written nCr or as a binomial coefficient).
  • A permutation (an ordered pick) of r out of n: n choices for the first, n − 1 for the second, …, n − r + 1 for the r-th.
  • Factorial: n! = 1 · 2 · 3 · … · n, and by agreement 0! = 1. 5! = 120.
  • Ordered picks = n · (n−1) · … · (n−r+1) = n! / (n−r)!.
  • Each team of r players appears r! times among the ordered picks (once per ordering of its players), so

C(n, r) = n! / ( r! · (n−r)! )

  • Example: C(5, 2) = 120 / (2 · 6) = 10, matching the hand list AB AC AD AE BC BD BE CD CE DE.
  • Edge cases: C(n, 0) = C(n, n) = 1 (one way to pick nobody, one way to pick everybody), and C(n, r) = 0 when r > n or r < 0 (impossible).

Problem X · Squad Picks

Problem X · Squad Picks (written for this course). A cricket academy gets q questions. Each gives n players and a squad size r. Print the number of ways to pick the squad, modulo 10^9 + 7.

1 ≤ q ≤ 10^5, 0 ≤ n, r ≤ 10^6, time limit 2 seconds.

Sample input Sample output
4 / 5 2 / 25 11 / 30 15 / 3 5 10 / 4457400 / 155117520 / 0

Extra edge cases: 0 0 → 1, 1000000 500000 → 996692777, 1000000 1000000 → 1.

Brute force 1: factorials in long long (wrong answers)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll fact(int n) {
    ll f = 1;
    for (int i = 2; i <= n; i++) f *= i;
    return f;
}

int main() {
    int n, r;
    cin >> n >> r;
    cout << fact(n) / (fact(r) * fact(n - r)) << "\n";
    return 0;
}
Input Output Correct answer
5 2 10 10
20 10 184756 184756
21 10 -29335 352716
25 11 2 4457400

Why: the largest long long is 9223372036854775807 ≈ 9.2·10^18. 20! ≈ 2.43·10^18 still fits, but 21! ≈ 5.1·10^19 does not: it overflows (wraps around), and from then on every number is garbage (even negative).

Why not just take everything mod p? Multiplication and addition survive a mod, but division does not: (a mod p) / (b mod p) is not (a / b) mod p. 6 / 3 = 2, but mod 5, 6 becomes 1, and 1 / 3 is not even a whole number. Two ways out: avoid division (Pascal), or divide with the modular inverse from episode 22.

Brute force 2: Pascal's triangle (memory)

Pascal's rule: C(n, r) = C(n−1, r−1) + C(n−1, r). Proof by the captain's question: look at the last player; either they are in (choose r − 1 more from n − 1) or out (choose all r from n − 1). It uses only additions, so taking mod p is safe.

Written in rows, it is Pascal's triangle: each cell is the cell up-left plus the cell straight up.

n C(n, 0) … C(n, n)
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007, N = 5000;
int C[N + 1][N + 1];

int main() {
    for (int i = 0; i <= N; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
    int q;
    cin >> q;
    while (q--) {
        int n, r;
        cin >> n >> r;
        cout << (r > n ? 0 : C[n][r]) << "\n";
    }
    return 0;
}

Output on the sample: 10, 4457400, 155117520, 0: correct, even past the overflow. (The table is 5001 · 5001 ints ≈ 100 MB.)

With N = 1000000 the program compiles, but crashes at once: Segmentation fault (exit code 139; the SyntaxPilot compiler and judges show Runtime Error (SIGSEGV)). The table needs 10^12 ints = 4 TB of memory, and filling it would take about 5·10^11 additions anyway. Pascal is O(n²) time and memory: great for n up to a few thousand, hopeless for 10^6.

The fix: factorials and inverse factorials mod p

From episode 22: p = 10^9 + 7 is prime, so dividing by x mod p is the same as multiplying by its modular inverse x^(p−2) mod p (Fermat's little theorem). So

C(n, r) mod p = n! · (r!)^(−1) · ((n−r)!)^(−1) mod p.

Precompute two arrays ("charts") once:

  • f[i] = i! mod p for i = 0 … N: f[0] = 1, f[i] = f[i−1] · i % p. N multiplications.
  • inv[i] = (i!)^(−1) mod p, the inverse factorial.

The backward trick. Calling a Fermat power for every i costs about N · 30 steps. Neater: since i! = i · (i−1)!, we get 1/(i−1)! = i / i!, so

inv[N] = power(f[N], p − 2) (one power call), then inv[i−1] = inv[i] · i % p walking down.

Total precomputation O(N + log p); every query is f[n] * inv[r] % p * inv[n − r] % p: O(1).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000000;  const ll MOD = 1000000007;
ll f[N + 1], inv[N + 1];      // n! and 1/n! mod p

ll power(ll a, ll e) {
    ll r = 1;
    for (a %= MOD; e > 0; e >>= 1, a = a * a % MOD)
        if (e & 1) r = r * a % MOD;
    return r;
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return f[n] * inv[r] % MOD * inv[n - r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    f[0] = 1;
    for (int i = 1; i <= N; i++) f[i] = f[i - 1] * i % MOD;
    inv[N] = power(f[N], MOD - 2);
    for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
    int q;
    cin >> q;
    while (q--) {
        int n, r;
        cin >> n >> r;
        cout << nCr(n, r) << "\n";
    }
    return 0;
}
Input Output
4 / 5 2 / 25 11 / 30 15 / 3 5 10 / 4457400 / 155117520 / 0
3 / 0 0 / 1000000 500000 / 1000000 1000000 1 / 996692777 / 1
10^5 random queries with n ≤ 10^6 about 0.05 s

Notes on the code:

  • f and inv are global: two arrays of 10^6 + 1 long long (16 MB) would overflow the stack inside main (episode 20).
  • Every product of two residues (numbers below p ≈ 10^9) can reach 10^18, so they must be long long.
  • nCr returns 0 for r < 0 || r > n before touching the arrays.
  • ios::sync_with_stdio(false); cin.tie(nullptr); is the fast I/O from episode 2.

Stress test: trust, but check

996692777 can't be checked by hand. So compare two completely different methods (episode 5): Pascal's triangle, which uses only additions, and the factorial formula, on every pair n ≤ 1000.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000;  const ll MOD = 1000000007;
ll f[N + 1], inv[N + 1], C[N + 1][N + 1];

ll power(ll a, ll e) {
    ll r = 1;
    for (a %= MOD; e > 0; e >>= 1, a = a * a % MOD)
        if (e & 1) r = r * a % MOD;
    return r;
}

int main() {
    f[0] = 1;
    for (int i = 1; i <= N; i++) f[i] = f[i - 1] * i % MOD;
    inv[N] = power(f[N], MOD - 2);
    for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
    int checked = 0;
    for (int n = 0; n <= N; n++)
        for (int r = 0; r <= n; r++) {
            C[n][r] = (r == 0 || r == n) ? 1
                    : (C[n - 1][r - 1] + C[n - 1][r]) % MOD;
            ll fast = f[n] * inv[r] % MOD * inv[n - r] % MOD;
            if (fast != C[n][r]) {
                cout << "MISMATCH " << n << " " << r << "\n";
                return 0;
            }
            checked++;
        }
    cout << "all " << checked << " pairs match\n";
    return 0;
}

Real output: all 501501 pairs match. (1001 · 1002 / 2 = 501501 pairs.)

Application 1 · Problem X2 · Rider Routes (grid paths)

Problem X2 · Rider Routes (written for this course). A delivery rider goes a blocks east and b blocks north through a city grid, never going west or south. How many shortest routes are there, mod 10^9 + 7? 0 ≤ a, b ≤ 5·10^5.

Every route is a + b moves, a of them East. For a = b = 2: EENN, ENEN, ENNE, NEEN, NENE, NNEE: 6. Choosing which a moves are East decides the route, so the answer is C(a + b, a).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000000;  const ll MOD = 1000000007;
ll f[N + 1], inv[N + 1];      // n! and 1/n! mod p

ll power(ll a, ll e) {
    ll r = 1;
    for (a %= MOD; e > 0; e >>= 1, a = a * a % MOD)
        if (e & 1) r = r * a % MOD;
    return r;
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return f[n] * inv[r] % MOD * inv[n - r] % MOD;
}

int main() {
    f[0] = 1;
    for (int i = 1; i <= N; i++) f[i] = f[i - 1] * i % MOD;
    inv[N] = power(f[N], MOD - 2);
    for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
    int a, b;
    cin >> a >> b;                 // blocks east, north
    cout << nCr(a + b, a) << "\n";
    return 0;
}
Input Output
2 2 6
3 2 10
0 7 1
500000 500000 996692777 (= C(10^6, 5·10^5), the same count)

Application 2 · Stars and bars

Share k identical items among m people, a person may get 0. Write the items as k stars and put m − 1 bars between them: ★★★ | ★★ | | ★★★★★ means 3, 2, 0, 5. Every sharing is exactly one arrangement of k stars and m − 1 bars in k + m − 1 slots, so

ways = C(k + m − 1, m − 1). 10 laddoos, 4 kids: C(13, 3) = 286 (checked by trying all sharings).

If every person must get at least one, give each one first and share the remaining k − m: C(k − 1, m − 1).

Complexity vs the constraints

Approach Precompute Per query Memory Verdict for q ≤ 10^5, n ≤ 10^6
Factorials in long long none O(n) O(1) Wrong Answer (overflow from n = 21)
Pascal's triangle mod p O(N²) ≈ 5·10^11 O(1) O(N²) = 4 TB Runtime Error (SIGSEGV) / MLE
Fermat power per query O(N) factorials O(log p) ≈ 30 O(N) OK (about 3·10^6 steps)
Factorials + inverse factorials O(N + log p) ≈ 2·10^6 O(1) O(N) = 16 MB Accepted, ≈ 0.05 s

The rule: many nCr queries mod a prime with n up to about 10^7: precompute f and inv once. Small n (≤ 5000) or a modulus that is not prime: Pascal's triangle.

Common mistakes (and the real outputs)

Bug 1: no check for r > n

ll nCr(int n, int r) {
    return f[n] * inv[r] % MOD * inv[n - r] % MOD;
}

Input 1 / 3 5 prints a garbage number instead of 0, and a different one on different runs (we saw -544706081, 39874410, -880022946 and 334369909). n − r = −2, so it reads inv[-2], memory outside the array: undefined behaviour. Fix: if (r < 0 || r > n) return 0;.

Bug 2: dividing residues

    return f[n] / (f[r] * f[n - r]) % MOD;

Input 5 2 and 25 11 prints 10 and then 0. Small cases pass because no factorial has wrapped yet (120 / 12 = 10), which is exactly why this bug survives the samples. Once the factorials are reduced mod p, normal division is meaningless. Fix: multiply by inv[r] and inv[n − r].

Bug 3: int charts

int f[N + 1], inv[N + 1];

Input 5 2 prints -162473916 instead of 10. The inverse factorials are arbitrary residues up to about 10^9, so inv[r] * inv[n − r] (or f[i-1] * i for big i) is computed in int and overflows before the % MOD. Fix: long long arrays (or cast: 1LL * a * b % MOD).

Summary table

Mistake What you see Why Fix
factorials in long long, no mod -29335 for 21 10, 2 for 25 11 21! overflows work mod p
no r > n check garbage for 3 5 reads inv[-2] if (r < 0 \|\| r > n) return 0;
f[n] / (f[r] * f[n - r]) % MOD 0 for 25 11 division doesn't survive mod multiply by inverses
int f[], inv[] -162473916 for 5 2 int · int overflows long long
Pascal with N = 10^6 Runtime Error (SIGSEGV) 4 TB table factorials + inverses

Mini project

Write a reusable combinatorics toolkit header: init(N) building f and inv, nCr, nPr (= f[n] · inv[n − r]), starsAndBars(k, m) and gridPaths(a, b). Test nCr against Pascal for n ≤ 1000 (like the stress test above), and starsAndBars against a brute force that tries every sharing for k, m ≤ 6.

Practice

These follow the video's homework.

  1. Compute C(n, 0) + C(n, 1) + … + C(n, n) mod p.

    Answer It is <b>2^n</b>: each of the n players is either in or out, and every subset has some size r. Use the fast power from episode 21: <code>power(2, n)</code>. For n = 5: 1 + 5 + 10 + 10 + 5 + 1 = 32.

  2. Share k laddoos among m kids so that every kid gets at least one.

    Answer Give each kid one first, then share the remaining k − m freely: C((k − m) + m − 1, m − 1) = <b>C(k − 1, m − 1)</b> (0 if k < m). 10 laddoos, 4 kids: C(9, 3) = 84, checked by brute force.

  3. Count grid routes from (0, 0) to (a, b) that avoid one blocked crossing (x, y).

    Answer All routes minus routes through (x, y): <b>C(a+b, a) − C(x+y, x) · C(a−x+b−y, a−x)</b>, mod p (add p before taking % to stay non-negative). For a = b = 3 and (1, 1): 20 − 2 · 6 = 8, checked with a DP over the grid. This "total minus bad" idea is next episode's inclusion-exclusion.

  4. Count teams of r out of n where players 1 and 2 refuse to play together.

    Answer All teams minus teams with both: <b>C(n, r) − C(n − 2, r − 2)</b>. n = 7, r = 3: 35 − 5 = 30, checked by listing all teams.

  5. Without code: what is C(6, 3), and which two cells of Pascal's triangle add up to it?

    Answer 20 = C(5, 2) + C(5, 3) = 10 + 10, the middle of row 6 (1 6 15 20 15 6 1).

Quick quiz

Five laddoos, three kids, a kid may get none. In how many ways? (nCr(5 + 3 - 1, 3 - 1))

A) 10 · B) 15 · C) 21 · D) 35

Answer

C. Five stars and two bars make seven slots: C(7, 2) = 7 · 6 / 2 = 21. D (35) is C(7, 3): it uses m instead of m − 1. A (10) is C(5, 2), forgetting the bars.

Interview questions

  1. Why can't you compute C(n, r) mod p as (n! mod p) / (r! mod p · (n−r)! mod p)? Division is not compatible with mod; you must multiply by the modular inverse instead.
  2. How do you get all inverse factorials in O(N)? Compute inv[N] = (N!)^(p−2) with one fast power, then inv[i−1] = inv[i] · i, because 1/(i−1)! = i / i!.
  3. When would you use Pascal's triangle instead? When n is small (a few thousand), or when the modulus is not prime (then inverses may not exist), since Pascal uses only additions.
  4. Why must the precomputation size N be at least the largest n you query? f[n] and inv[n] must exist; for grid paths that's a + b, not max(a, b).
  5. What is the number of shortest grid paths from (0,0) to (a,b)? C(a + b, a): choose which of the a + b moves go east.
  6. What does stars and bars count? Ways to split k identical items among m people: C(k + m − 1, m − 1).

Glossary

Term Meaning Example
Combination A choice of r items from n, order ignored {A, B} = {B, A}
C(n, r), "n choose r", nCr The number of combinations C(5, 2) = 10
Binomial coefficient Another name for C(n, r) the numbers in Pascal's triangle
Permutation (ordered pick) A choice where order matters AB ≠ BA: 20 ordered pairs from 5
Factorial n! 1 · 2 · … · n; 0! = 1 5! = 120
Overflow A value too big for its type wraps around 21! in long long → garbage
Modulus, mod p Keep only the remainder after dividing by p answers mod 10^9 + 7
Residue A number already reduced mod p, 0 … p − 1 6 mod 5 = 1
Modular inverse x^(−1): the number with x · x^(−1) ≡ 1 (mod p) 3^(−1) mod 7 = 5
Fermat's little theorem For prime p and x not divisible by p, x^(p−1) ≡ 1, so x^(−1) = x^(p−2) episode 22
Fast power a^e in O(log e) by squaring power(f[N], MOD - 2)
Inverse factorial (i!)^(−1) mod p inv[i]
Pascal's rule C(n, r) = C(n−1, r−1) + C(n−1, r) 10 = 4 + 6
Pascal's triangle The table of C(n, r), each cell = up-left + up row 5: 1 5 10 10 5 1
Precomputation Work done once before the queries building f and inv
O(1) per query Constant work for each question three lookups
Stress test Compare a fast solution with a trusted slow one on many inputs 501501 pairs match
Grid path A shortest route on a grid using only right/up moves C(a + b, a)
Stars and bars k items, m − 1 dividers: C(k + m − 1, m − 1) 10 laddoos, 4 kids: 286
Undefined behaviour C++ code with no defined result, like reading outside an array inv[-2]
Segmentation fault (SIGSEGV) Crash from touching memory the program doesn't own a 4 TB global table

Summary

  • C(n, r) = n! / (r! (n−r)!) counts choices without order; C(n, r) = 0 when r > n.
  • Factorials in long long overflow from 21! (21 10 → -29335).
  • Pascal's rule needs only additions, so it is safe mod p, but the table is O(n²): N = 10^6 needs 4 TB (SIGSEGV).
  • Precompute f[i] = i! mod p, inv[N] = f[N]^(p−2), inv[i−1] = inv[i] · i; then nCr = f[n] · inv[r] · inv[n−r] in O(1). A stress test matched Pascal on all 501501 pairs with n ≤ 1000.
  • Grid paths: C(a + b, a). Stars and bars: C(k + m − 1, m − 1).
  • Real bugs: missing r > n check (garbage), dividing residues (0), int products (-162473916).

Solutions in C++, Java and Python

Problem X · Squad Picks

C++: the factorial + inverse factorial program above.

Java (tested: the sample → 10 4457400 155117520 0; 0 0, 1000000 500000, 1000000 1000000 → 1 996692777 1; 10^5 random queries: identical output to the C++ program, about 0.25 s). StreamTokenizer reads numbers fast (ints up to 10^6 fit its double exactly), and all output goes into one StringBuilder.

import java.io.*;
import java.util.*;

public class Main {
    static final int N = 1000000;
    static final long MOD = 1000000007L;
    static long[] f = new long[N + 1], inv = new long[N + 1];

    static long power(long a, long e) {
        long r = 1;
        a %= MOD;
        while (e > 0) {
            if ((e & 1) == 1) r = r * a % MOD;
            a = a * a % MOD;
            e >>= 1;
        }
        return r;
    }

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

    public static void main(String[] args) throws IOException {
        f[0] = 1;
        for (int i = 1; i <= N; i++) f[i] = f[i - 1] * i % MOD;
        inv[N] = power(f[N], MOD - 2);
        for (int i = N; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st = new StreamTokenizer(br);
        st.nextToken();
        int q = (int) st.nval;
        StringBuilder out = new StringBuilder();
        while (q-- > 0) {
            st.nextToken(); int n = (int) st.nval;
            st.nextToken(); int r = (int) st.nval;
            out.append(nCr(n, r)).append('\n');
        }
        System.out.print(out);
    }
}

Python (tested on the same inputs: same outputs, and identical to C++ on the 10^5 random queries in about 0.7 s). Python ints never overflow, but the arrays are built only up to the largest n asked, and the built-in pow(x, e, m) is the fast power.

import sys

MOD = 10**9 + 7

def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    qs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(q)]
    N = max([n for n, _ in qs] + [0])     # build only as far as needed
    f = [1] * (N + 1)
    for i in range(1, N + 1):
        f[i] = f[i - 1] * i % MOD
    inv = [1] * (N + 1)
    inv[N] = pow(f[N], MOD - 2, MOD)      # Python's built-in fast power
    for i in range(N, 0, -1):
        inv[i - 1] = inv[i] * i % MOD
    out = []
    for n, r in qs:
        if r < 0 or r > n:
            out.append(0)
        else:
            out.append(f[n] * inv[r] % MOD * inv[n - r] % MOD)
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Problem X2 · Rider Routes

C++: the Rider Routes program above. In Java or Python, reuse the Squad Picks charts (with N ≥ a + b) and print nCr(a + b, a): 2 2 → 6, 3 2 → 10, 500000 500000 → 996692777.

Next episode: Inclusion-exclusion.