Matrix Exponentiation

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; struct Matrix { int n; vector<vector<ll>> mat; Matrix(int _n, bool identity = false) : n(_n), mat(_n, vector<ll>(_n, 0)) { if (identity) for (int i = 0; i < n; i++) mat[i][i] = 1; } Matrix operator*(const Matrix &o) const { Matrix res(n); for (int i = 0; i < n; i++) for (int k = 0; k < n; k++) { if (!mat[i][k]) continue; for (int j = 0; j < n; j++) res.mat[i][j] = (res.mat[i][j] + mat[i][k] * o.mat[k][j]) % MOD; } return res; } Matrix pow(ll e) const { Matrix res(n, true), base = *this; while (e > 0) { if (e & 1) res = res * base; base = base * base; e >>= 1; } return res; } };

Compute $M^k$ for an $n \times n$ matrix using binary exponentiation in $O(n^3 \log k)$ .

How It Works

Same idea as scalar binary exponentiation but with matrix multiplication:

Start with identity matrix

I

Decompose

k

in binary, square

M

repeatedly, multiply into result when bit is 1

Recurrence to Matrix

For a linear recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}$ , define:

A = \begin{pmatrix} c_1 & c_2 & \cdots & c_k \\ 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & & \ddots & 0 \end{pmatrix}

Then $v_n = A^n \cdot v_0$ where $v_0$ is the initial state vector.

When to Use

Fibonacci / Lucas numbers for

n

up to

10^{18}

Any fixed-order linear recurrence where

n

is too large for DP

Counting paths of length

k

in a graph via adjacency matrix powers

State machine transitions raised to a large power

Complexity

Time —

O(n^3 \log k)

where

n

is matrix size and

k

is exponent

Space —

O(n^2)