Chapter 90

Home

Matrix Exponentiation

Linear recurrences (like Fibonacci) can be expressed as matrix multiplication. Computing Mᴺ via fast exponentiation gives the Nth term in O(K³ log N) for a K×K matrix — compared to O(N) for iterative DP.

Fibonacci via Matrix

[F(n)  ]   = [1 1]^(n-1)  × [F(1)]
[F(n-1)]     [1 0]         [F(0)]

Where F(0)=0, F(1)=1.
Matrix size: 2×2 → O(8 log N) multiplications.

C++ — Fibonacci via matrix exponentiation

using Matrix = vector>;

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

Matrix pow(Matrix M, long long exp, long long MOD) {
    int n = M.size();
    Matrix R(n, vector(n, 0));
    for (int i = 0; i < n; i++) R[i][i] = 1;
    while (exp > 0) {
        if (exp & 1) R = mul(R, M, MOD);
        M = mul(M, M, MOD);
        exp >>= 1;
    }
    return R;
}

long long fib_matrix(long long n, long long MOD) {
    if (n <= 1) return n;
    Matrix M = {{1, 1}, {1, 0}};
    auto R = pow(M, n - 1, MOD);
    return R[0][0];
}

// O(log N) — N can be 10^18!

💡 Any linear recurrence works

f(n) = a₁f(n-1) + a₂f(n-2) + ... + aₖf(n-k) → K×K companion matrix. O(K³ log N). Use this when N is too large for iterative DP (N ≤ 10¹⁸ is common).

Key Takeaways