Pattern Guide
Matrix Exponentiation
"Compute linear recurrences in O(k³ log n). Fibonacci in O(log n)."
Matrix exponentiation computes the n-th term of a linear recurrence in O(k³ log n) where k is the recurrence order. Write the recurrence as a matrix multiplication T·v = v', then T^n·v₀ = vₙ. Uses fast matrix power (repeated squaring). Solves: Fibonacci, tribonacci, counting paths of length n in a graph, tiling problems, and any k-th order linear recurrence.
Problems you can solve with this pattern
4 problems · click any to start solving
const MOD = BigInt(1e9 + 7);
function matMul(A, B) {
const n = A.length, m = B[0].length, k = B.length;
const C = Array.from({length: n}, () => new Array(m).fill(0n));
for (let i = 0; i < n; i++)
for (let l = 0; l < k; l++) if (A[i][l])
for (let j = 0; j < m; j++)
C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % MOD;
return C;
}
function matPow(M, p) {
let n = M.length;
// Identity matrix
let result = Array.from({length: n}, (_, i) => Array.from({length: n}, (_, j) => i === j ? 1n : 0n));
while (p > 0n) {
if (p & 1n) result = matMul(result, M);
M = matMul(M, M);
p >>= 1n;
}
return result;
}
// Fibonacci: T = [[1,1],[1,0]], T^n * [1,0]^T = [F(n+1), F(n)]^T
function fibonacci(n) {
if (n <= 1) return BigInt(n);
const T = [[1n, 1n], [1n, 0n]];
const Tn = matPow(T, BigInt(n - 1));
return Tn[0][0]; // F(n)
}Any k-th order linear recurrence f(n) = a₁f(n-1) + a₂f(n-2) + ... + aₖf(n-k) can be written as a matrix multiplication: [[a₁,a₂,...,aₖ],[1,0,...,0],...,[0,...,1,0]] × [f(n-1),f(n-2),...,f(n-k)]ᵀ = [f(n),...,f(n-k+1)]ᵀ. Raise this matrix to the n-th power using fast exponentiation (repeated squaring) to get f(n) in O(k³ log n) multiplications.
const MOD = BigInt(1e9 + 7);
function matMul(A, B) {
const n = A.length, m = B[0].length, k = B.length;
const C = Array.from({length: n}, () => new Array(m).fill(0n));
for (let i = 0; i < n; i++)
for (let l = 0; l < k; l++) if (A[i][l])
for (let j = 0; j < m; j++)
C[i][j] = (C[i][j] + A[i][l] * B[l][j]) % MOD;
return C;
}
function matPow(M, p) {
let n = M.length;
// Identity matrix
let result = Array.from({length: n}, (_, i) => Array.from({length: n}, (_, j) => i === j ? 1n : 0n));
while (p > 0n) {
if (p & 1n) result = matMul(result, M);
M = matMul(M, M);
p >>= 1n;
}
return result;
}
// Fibonacci: T = [[1,1],[1,0]], T^n * [1,0]^T = [F(n+1), F(n)]^T
function fibonacci(n) {
if (n <= 1) return BigInt(n);
const T = [[1n, 1n], [1n, 0n]];
const Tn = matPow(T, BigInt(n - 1));
return Tn[0][0]; // F(n)
}- n-th term of a linear recurrence with n up to 10^18
- Count paths of exactly length k in a graph (adjacency matrix ^ k)
- Any DP where state transitions are fixed and independent of position
Template: Write recurrence as T·v = v'. Compute T^n via repeated squaring. O(k³ log n).
Common recurrences:
- Fibonacci: T = [[1,1],[1,0]]
- Tribonacci: T = [[1,1,1],[1,0,0],[0,1,0]]
- String DP (e.g. vowel permutation): each character = one matrix multiply
Modular arithmetic: Use BigInt or handle overflow carefully in JavaScript for large mod values.