Chapter 7 · Matrices
Linear Recurrences from Graphs and Matrices
Turn a DP with constant-size state into a matrix, exponentiate, and answer n = 10^18 questions.
Every DP of the form "the state at step i is a fixed-size vector, and each entry is a linear combination of the previous step's entries" is a matrix power in disguise — so anything with n ≤ 1018 and a small state is solvable.
binom{Fk+1}{Fk} = C(1, 1)C(1, 0)kC(1, 0) — i.e. M = 1 & 1; 1 & 0, Mk gives Fk+1 in O(log k). The point is not Fibonacci; it is that the transition matrix is the recurrence.
- 1
Write the DP state as a vector vi of constant size k (window of the last values, or the "profile" of a board column, or the automaton state count).
- 2
Write vi+1 = T vi by reading the recurrence's coefficients — row j of T says how vi+1[j] is formed.
- 3
Answer = entry of T n - i0 vi0, computed by binary exponentiation mod M in O(k3 log n).
- 4
If there are several "queries with different n", precompute T20, …, T^{260} once: O(k3 log n) memory, O(k2 log n) per query.
// k-th order recurrence f(n) = c[0] f(n-1) + ... + c[k-1] f(n-k), n up to 1e18
using Mat = vector<vector<ll>>;
Mat T(k, vector<ll>(k));
for (int j = 0; j < k; j++) T[0][j] = c[j]; // companion matrix
for (int i = 1; i < k; i++) T[i][i - 1] = 1;
Mat P = mpow(T, n - (k - 1), MOD);
ll ans = 0;
for (int j = 0; j < k; j++) ans = (ans + P[0][j] * base[j]) % MOD; // base = f(k-1), ..., f(0)Recurrences that come from graphs
- walks of length ≤ k between two vertices: adjacency powers (Counting Walks with Matrix Powers);
- number of independent sets / matchings in a path or cycle graph: transfer matrix of width 2–3, which is also the "domino tiling of a 3 × n board" trick (state = which cells of the current column are already covered — 2b states for height b, so b ≤ 12 is comfortable),
- expected first hitting time in a Markov chain: solve (I - Q)x = rhs, i.e. a linear system rather than a power (Random Walks and Cover Times),
- graph power queries "is there a path of length exactly k in a graph with self-loops at every vertex": Ak with A + I.
If you can compute f(0), f(1), …, f(2L) by DP for small arguments (say L = 200), Berlekamp–Massey recovers the minimal linear recurrence of order ≤ L in O(L2) over a field, and you then exponentiate as above. This is a legitimate competitive-programming technique for "count tilings/walks modulo 109+7 with n ≤ 109 and a state you can enumerate": guess-and-prove is replaced by a theorem (the recurrence is minimal, hence unique mod p for the sequence's first 2L terms).
If T is sparse (typical for automaton transitions), do matrix–vector exponentiation instead: precompute T2i is O(k3) each, but applying bits to a vector is O(k2) — total O(k3 log n + k2 log n). For k = 100 and one query it does not matter; for 105 queries with the same T the precompute amortises and you never multiply two matrices again.
- Tn mod M with composite M: no problem, but if you instead want to divide (e.g. closed form with √5), you need M prime and an inverse — or lift to ℤM[x]/(x2 - 5).
- Recurrences whose natural state has O(n) entries (n = problem size): the matrix is then n × n and O(n3 log k) beats the O(nk) DP only for k ≫ n. Do the arithmetic before writing code — that check is the skill.
- f(n) = f(n-1) + 2 f(n-3) with f(0)=f(1)=f(2)=1: write the 3× 3 transition matrix and compute f(10) by hand-modulo-1000, then verify against the DP.
- Number of ways to tile a 3 × n rectangle with dominoes: derive the 8-state (or 4-state) transfer matrix, and the order-2 recurrence an = 4an-2 - an-4 you get after eliminating states.