Compute combinations with Pascal’s identity
Build exact or modular answers using addition instead of unsafe factorial division.
Understand the idea
Pick one distinguished person. Groups of size r either include that person and choose r − 1 others, or exclude them and choose r others. Thus C(n, r) = C(n − 1, r − 1) + C(n − 1, r). Boundary entries C(n, 0) and C(n, n) are 1.
Trace a small example
Row 4 is 1, 4, 6, 4, 1. In a one-dimensional table, update r downward so both inputs still belong to the previous row. Updating upward would reuse values already changed in the current row.
#include <iostream>
#include <vector>
int main() {
const int n = 5, r = 2;
std::vector<long long> choose(r + 1, 0);
choose[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = (i < r ? i : r); j >= 1; --j)
choose[j] += choose[j - 1];
std::cout << choose[r] << '\n';
}Conditions and cost
A full table costs O(N²) time and memory. A truncated row uses O(r) space and O(nr) time. Reducing after additions works for any positive modulus; no modular inverse is required. Exact signed-64-bit examples here use n ≤ 60.
Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
Why update a one-row Pascal table from right to left?
Turn the idea into code
Compute C(5, 2) from the previous row.
Give me a hint
Use C(4, 1) and C(4, 2).
Show the explained solution
C(5, 2) = 4 + 6 = 10.
Your notes
Mark complete when you can explain it yourself.