Chapter 29 of 30

Modular Inverse, Combinatorics & Fast Math

Master modular inverse, computing C(N,K) mod M, common combinatorial problems, and matrix exponentiation.

Modular Multiplicative InverseCombinatorics: C(N, K) mod MCommon Combinatorial ProblemsMatrix Exponentiation (Fast Math)

Modular Inverse, Combinatorics & Fast Math

Combinatorics counts arrangements. When the answer is large, we compute it modulo a prime. This chapter covers the tools you need.

Modular Multiplicative Inverse

The inverse of a modulo m is the number x such that a × x ≡ 1 (mod m).

Fermat's Little Theorem (When m is Prime)

code

a^(m-1) ≡ 1 (mod m)
Therefore: a^(-1) ≡ a^(m-2) (mod m)

hljs cpp

const int MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modInverse(long long a) {
    return power(a, MOD - 2, MOD);
}

Extended Euclidean Algorithm (When m is Not Prime)

hljs cpp

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = extGCD(a, m, x, y);
    if (g != 1) return -1;  // no inverse
    return (x % m + m) % m;
}

Combinatorics: C(N, K) mod M

code

C(N, K) = N! / (K! × (N-K)!)

Precompute Factorials

hljs cpp

const int MAX = 200001;
long long fact[MAX], invFact[MAX];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invFact[MAX - 1] = power(fact[MAX - 1], MOD - 2, MOD);
    for (int i = MAX - 2; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * invFact[k] % MOD * invFact[n - k] % MOD;
}

Time Complexity

O(MAX) preprocessing, O(1) per query.

Common Combinatorial Problems

Number of Ways to Partition n into k Parts

code

C(n-1, k-1)  (stars and bars)

Number of Paths in a Grid

To go from (0,0) to (n,m), you need n down moves and m right moves:

code

C(n+m, n) = C(n+m, m)

Catalan Numbers

Number of valid parenthesizations, BSTs, and many other structures:

code

C(2n, n) / (n+1)

hljs cpp

long long catalan(int n) {
    return C(2 * n, n) % MOD * modInverse(n + 1) % MOD;
}

Derangements

Permutations where no element is in its original position:

code

D(0) = 1
D(1) = 0
D(n) = (n-1) * (D(n-1) + D(n-2))

hljs cpp

long long derangement(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    long long a = 1, b = 0;  // D(0), D(1)
    for (int i = 2; i <= n; i++) {
        long long c = (i - 1) * (b + a) % MOD;
        a = b;
        b = c;
    }
    return b;
}

Inclusion-Exclusion

Count elements in the union of sets:

code

|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Matrix Exponentiation (Fast Math)

Compute matrix powers in O(k³ log n) where k is the matrix size:

hljs cpp

typedef vector<vector<long long>> Matrix;

Matrix multiply(const Matrix &A, const Matrix &B) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

Matrix power(Matrix base, long long exp) {
    int n = base.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1;  // identity
    
    while (exp > 0) {
        if (exp & 1) result = multiply(result, base);
        base = multiply(base, base);
        exp >>= 1;
    }
    return result;
}

Fibonacci with Matrix Exponentiation

code

| F(n+1) |   | 1  1 |   | F(n) |
| F(n)   | = | 1  0 | × | F(n-1) |

hljs cpp

long long fib(long long n) {
    if (n <= 1) return n;
    Matrix base = {{1, 1}, {1, 0}};
    Matrix result = power(base, n);
    return result[0][1];
}

Summary

Modular inverse: a^(m-2) mod m when m is prime (Fermat's Little Theorem)
Precompute factorials and inverse factorials for O(1) combination queries
C(n, k) = n! / (k! × (n-k)!) — use precomputed factorials
Catalan numbers, derangements, and inclusion-exclusion are common patterns
Matrix exponentiation: O(k³ log n) for linear recurrences (Fibonacci, etc.)

Ch 28: Backtracking & Meet-in-the-Middle Ch 30: Hashing, String Algorithms & Geometry Basics

Prefer reading offline? Download the full book as a PDF.

Download Free Book

Chapter 29 of 30

Modular Inverse, Combinatorics & Fast Math

Master modular inverse, computing C(N,K) mod M, common combinatorial problems, and matrix exponentiation.

Modular Multiplicative InverseCombinatorics: C(N, K) mod MCommon Combinatorial ProblemsMatrix Exponentiation (Fast Math)

Modular Inverse, Combinatorics & Fast Math

Combinatorics counts arrangements. When the answer is large, we compute it modulo a prime. This chapter covers the tools you need.

Modular Multiplicative Inverse

The inverse of a modulo m is the number x such that a × x ≡ 1 (mod m).

Fermat's Little Theorem (When m is Prime)

code

a^(m-1) ≡ 1 (mod m)
Therefore: a^(-1) ≡ a^(m-2) (mod m)

hljs cpp

const int MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modInverse(long long a) {
    return power(a, MOD - 2, MOD);
}

Extended Euclidean Algorithm (When m is Not Prime)

hljs cpp

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = extGCD(a, m, x, y);
    if (g != 1) return -1;  // no inverse
    return (x % m + m) % m;
}

Combinatorics: C(N, K) mod M

code

C(N, K) = N! / (K! × (N-K)!)

Precompute Factorials

hljs cpp

const int MAX = 200001;
long long fact[MAX], invFact[MAX];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    invFact[MAX - 1] = power(fact[MAX - 1], MOD - 2, MOD);
    for (int i = MAX - 2; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * invFact[k] % MOD * invFact[n - k] % MOD;
}

Time Complexity

O(MAX) preprocessing, O(1) per query.

Common Combinatorial Problems

Number of Ways to Partition n into k Parts

code

C(n-1, k-1)  (stars and bars)

Number of Paths in a Grid

To go from (0,0) to (n,m), you need n down moves and m right moves:

code

C(n+m, n) = C(n+m, m)

Catalan Numbers

Number of valid parenthesizations, BSTs, and many other structures:

code

C(2n, n) / (n+1)

hljs cpp

long long catalan(int n) {
    return C(2 * n, n) % MOD * modInverse(n + 1) % MOD;
}

Derangements

Permutations where no element is in its original position:

code

D(0) = 1
D(1) = 0
D(n) = (n-1) * (D(n-1) + D(n-2))

hljs cpp

long long derangement(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;
    long long a = 1, b = 0;  // D(0), D(1)
    for (int i = 2; i <= n; i++) {
        long long c = (i - 1) * (b + a) % MOD;
        a = b;
        b = c;
    }
    return b;
}

Inclusion-Exclusion

Count elements in the union of sets:

code

|A ∪ B| = |A| + |B| - |A ∩ B|
|A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

Matrix Exponentiation (Fast Math)

Compute matrix powers in O(k³ log n) where k is the matrix size:

hljs cpp

typedef vector<vector<long long>> Matrix;

Matrix multiply(const Matrix &A, const Matrix &B) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

Matrix power(Matrix base, long long exp) {
    int n = base.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1;  // identity
    
    while (exp > 0) {
        if (exp & 1) result = multiply(result, base);
        base = multiply(base, base);
        exp >>= 1;
    }
    return result;
}

Fibonacci with Matrix Exponentiation

code

| F(n+1) |   | 1  1 |   | F(n) |
| F(n)   | = | 1  0 | × | F(n-1) |

hljs cpp

long long fib(long long n) {
    if (n <= 1) return n;
    Matrix base = {{1, 1}, {1, 0}};
    Matrix result = power(base, n);
    return result[0][1];
}

Summary

Modular inverse: a^(m-2) mod m when m is prime (Fermat's Little Theorem)
Precompute factorials and inverse factorials for O(1) combination queries
C(n, k) = n! / (k! × (n-k)!) — use precomputed factorials
Catalan numbers, derangements, and inclusion-exclusion are common patterns
Matrix exponentiation: O(k³ log n) for linear recurrences (Fibonacci, etc.)

Ch 28: Backtracking & Meet-in-the-Middle Ch 30: Hashing, String Algorithms & Geometry Basics

Prefer reading offline? Download the full book as a PDF.

Download Free Book