---
title: "Linear Recurrences from Graphs and Matrices"
summary: Turn a DP with constant-size state into a matrix, exponentiate, and answer n = 10^18 questions.
difficulty: hard
tags: [recurrence, exponentiation, DP]
time: k^3 log n
space: k^2
prereq: [matrices/walks-powers]
see: [matrices/matrix-tree, special/random-walk]
---

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 \le 10^{18}$ and a small state is solvable.

:::example title="Fibonacci, properly"
$\binom{F_{k+1}}{F_k} = \binom{1}{1}\binom{1}{0}^{k}\binom{1}{0}$ — i.e. $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$, $M^k$ gives $F_{k+1}$ in $O(\log k)$. The point is not Fibonacci; it is that *the transition matrix is the recurrence*.
:::

:::steps title="The recipe, for any problem of this shape"
1. Write the DP state as a vector $v_i$ of constant size $k$ (window of the last values, or the "profile" of a board column, or the automaton state count).
2. Write $v_{i+1} = T v_i$ by reading the recurrence's coefficients — row $j$ of $T$ says how $v_{i+1}[j]$ is formed.
3. Answer $= $ entry of $T^{\,n - i_0} v_{i_0}$, computed by binary exponentiation mod $M$ in $O(k^3 \log n)$.
4. If there are several "queries with different $n$", precompute $T^{2^0}, \dots, T^{2^{60}}$ once: $O(k^3 \log n)$ memory, $O(k^2 \log n)$ per query.
:::

```cpp linear-recurrence.cpp
// 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)
```

:::props title="Recurrences that come from graphs"
- **walks of length $\le k$ between two vertices**: adjacency powers (@matrices/walks-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 \times n$ board" trick (state = which cells of the current column are already covered — $2^b$ states for height $b$, so $b \le 12$ is comfortable),
- **expected first hitting time in a Markov chain**: solve $(I - Q)x = \text{rhs}$, i.e. a linear system rather than a power (@special/random-walk),
- **graph power queries** "is there a path of length exactly $k$ in a graph with self-loops at every vertex": $A^k$ with $A + I$.
:::

:::note title="When the order is not constant: Berlekamp–Massey"
If you can *compute* $f(0), f(1), \dots, f(2L)$ by DP for small arguments (say $L = 200$), Berlekamp–Massey recovers the minimal linear recurrence of order $\le L$ in $O(L^2)$ over a field, and you then exponentiate as above. This is a legitimate competitive-programming technique for "count tilings/walks modulo $10^9+7$ with $n \le 10^9$ 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).
:::

:::example title="Sparse $T$, huge $k$"
If $T$ is sparse (typical for automaton transitions), do **matrix–vector** exponentiation instead: precompute $T^{2^i}$ is $O(k^3)$ each, but applying bits to a vector is $O(k^2)$ — total $O(k^3 \log n + k^2 \log n)$. For $k = 100$ and one query it does not matter; for $10^5$ queries with the same $T$ the precompute amortises and you never multiply two matrices again.
:::

:::warning title="Two modulus traps"
1. $T^n \bmod M$ with composite $M$: no problem, but if you instead want to divide (e.g. closed form with $\sqrt5$), you need $M$ prime and an inverse — or lift to $\mathbb{Z}_M[x]/(x^2 - 5)$.
2. Recurrences whose natural state has $O(n)$ entries ($n$ = problem size): the matrix is then $n \times n$ and $O(n^3 \log k)$ beats the $O(nk)$ DP only for $k \gg n$. Do the arithmetic before writing code — that check *is* the skill.
:::

:::problems
- [[CSES 2181]] Counting Tilings | https://cses.fi/problemset/task/2181 | hard | transfer matrix, $2^b$ states
:::

:::exercise title="Do these by hand, then code them"
1. $f(n) = f(n-1) + 2 f(n-3)$ with $f(0)=f(1)=f(2)=1$: write the $3\times 3$ transition matrix and compute $f(10)$ by hand-modulo-1000, then verify against the DP.
2. Number of ways to tile a $3 \times n$ rectangle with dominoes: derive the 8-state (or 4-state) transfer matrix, and the order-2 recurrence $a_n = 4a_{n-2} - a_{n-4}$ you get after eliminating states.
:::