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 pfor 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:
fandinvare global: two arrays of 10^6 + 1long long(16 MB) would overflow the stack insidemain(episode 20).- Every product of two residues (numbers below p ≈ 10^9) can reach 10^18, so they must be
long long. nCrreturns 0 forr < 0 || r > nbefore 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.
-
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. -
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. -
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. -
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. -
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
- 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.
- 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!.
- 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.
- 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).
- 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.
- 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 longoverflow 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 > ncheck (garbage), dividing residues (0),intproducts (-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.