Matrix Exponentiation for Linear Recurrences
Climbing stairs one or two steps at a time: how many ways to reach step 50? A loop of 50 additions answers that instantly. Now make it step , answer modulo . The same loop would need iterations. At a billion iterations per second that is about 31.7 years.
This lesson shows how to get that answer in 60 squarings of a 2×2 matrix — well under a microsecond of real work. The trick is general. Whenever one step of a DP turns a fixed-size list of numbers into the next list using only additions and multiplications by constants, that step is a matrix. Doing the step times is multiplying by the matrix times, which is the matrix to the power . And a power can be computed by repeated squaring in multiplications, exactly like computing by hand.
You will learn to:
- compute Fibonacci numbers in and prove why the matrix works,
- build the companion matrix for any linear recurrence, including ones with a constant term like "",
- count walks of length in a graph with ,
- count domino tilings of a (or ) board with a transfer matrix,
- avoid the overflow bugs that make this technique famous for wrong answers.
This lesson assumes you are comfortable with basic DP (state, transition, base case — see Grid & Path DP and DP Foundations), with proofs by induction (Recursion & Induction) and with arithmetic modulo a prime (Modular Arithmetic). You do not need a linear algebra course: the only matrix operation we use is multiplication, and it is defined from scratch below.
Why this exists
DP is usually about avoiding repeated work across different subproblems. Matrix exponentiation attacks a different bottleneck: a DP whose state is tiny (2, 3, maybe 100 numbers) but whose number of steps is astronomically large. The step itself is cheap; there are just too many of them.
The idea is old. Repeated squaring for powers of numbers appears in the Indian Chandaḥśāstra (before 200 BCE) and is analysed in Knuth's The Art of Computer Programming, Vol. 2, §4.6.3. The matrix form of Fibonacci, , is classical (it is sometimes called the "Q-matrix", studied by Charles King in 1960; see Gould's 1981 survey in The Fibonacci Quarterly). The transfer-matrix method for counting configurations on strips is a workhorse of statistical physics, going back to Kramers and Wannier (1941) for the Ising model.
In programming today, the technique shows up in three places:
- Competitive programming and interviews — "compute the -th term modulo , ".
- Random number generators — jumping a linear generator ahead by steps so that parallel threads get non-overlapping streams.
- Markov chains and graphs — the probability of being in state after steps is entry of , and the number of length- walks is an entry of .
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "" (or , or "huge ") and a simple recurrence | Matrix exponentiation of the recurrence's companion matrix |
| "" with small | companion matrix, |
| Same, but with "" or "" or "" | Add extra state entries that carry , or along |
| "number of walks / paths of exactly steps" in a small graph | (adjacency matrix to the ) |
| "shortest route using exactly edges" | in the min-plus semiring |
| "tile a / board", "color an grid" | Transfer matrix over column (or row) profiles, then power |
| "probability of being in state after steps" | Markov transition matrix |
| A DP whose state is a small fixed set and whose step is the same every time | That step is a matrix — exponentiate it |
| "sum of the first terms" of a linear recurrence | Add a running-sum entry to the state |
| Recurrence order in the thousands, huge | Kitamasa / polynomial methods (advanced, not covered in depth) |
The meta-trigger: the same linear step, applied many times, on a small state. If the step depends on in a non-linear way (like ), or uses min/max without a matching semiring, or the state grows with , plain matrix exponentiation does not apply.
Intuition & first principles
Fast powers of plain numbers
Start without matrices. How do you compute with few multiplications?
The slow way multiplies 3 by itself 12 times. The fast way notices that (binary 1101), so
And come from squaring the previous one: , , . Three squarings plus two extra multiplications instead of twelve. For an exponent the count is about squarings plus at most extra multiplications. For that is 60 squarings: has 60 binary digits.
This is binary exponentiation (also called exponentiation by squaring). It works for anything you can multiply associatively — where — because then and we may group the factors however we like. Numbers mod are associative. So are matrices.
A matrix is just "one DP step"
A matrix is a rectangular table of numbers. Multiplying a matrix by a column of numbers (a vector) gives a new column: entry of is "row of , multiplied entry-by-entry with , then summed". For a 2×2 matrix:
Now look at Fibonacci: , , . Keep the last two values as a vector . One DP step produces :
- new top ,
- new bottom .
Read off the coefficients and you have the matrix:
Do the step times starting from and you get . Matrix multiplication is associative, so we can compute first — by repeated squaring — and apply it once.
flowchart LR
V0["(F1, F0) = (1, 0)"] -->|"times M"| V1["(F2, F1) = (1, 1)"]
V1 -->|"times M"| V2["(F3, F2) = (2, 1)"]
V2 -->|"times M"| V3["(F4, F3) = (3, 2)"]
V3 -->|"... n times"| VN["(F(n+1), F(n))"]
V0 -.->|"times M^n, computed by squaring"| VN
The solid arrows are the ordinary DP: cheap steps. The dotted arrow is the same result in one jump, where the jump matrix took only matrix products to build.
Multiplying two matrices
To square a matrix we need matrix-times-matrix. Entry of is row of dotted with column of :
Example: .
The meaning: applying then to a vector is the same as applying once. So is "the combined step". A product takes multiplications ( entries, terms each).
Two facts make exponentiation legal:
- Associativity: . That is what lets us group .
- Identity: the identity matrix (1s on the diagonal, 0 elsewhere) satisfies . It plays the role of "1" as the starting value of the running product.
Matrix multiplication is not commutative in general (). Powers of the same matrix do commute with each other (), which is why the order of the extra multiplications in binary exponentiation does not matter here. It does matter when you multiply different matrices — for example, two different transition steps that alternate.
Mechanics
1. Binary exponentiation of a matrix
mat_pow(M, e):
R = I # running result
B = M # B = M^(2^i) at loop iteration i
while e > 0:
if e is odd: R = R * B # this bit of e is 1: include B
B = B * B # move to the next power of two
e = e // 2
return R
Dry run for , . We read the bits from the lowest. Numbers are small, so no modulus yet.
| Iteration | Bit of 13 | B at start of iteration | Action on R | R after | R is |
|---|---|---|---|---|---|
| start | — | = [[1,1],[1,0]] | — | [[1,0],[0,1]] | |
| 0 | 1 | = [[1,1],[1,0]] | R = R·B | [[1,1],[1,0]] | |
| 1 | 0 | = [[2,1],[1,1]] | skip | [[1,1],[1,0]] | |
| 2 | 1 | = [[5,3],[3,2]] | R = R·B | [[8,5],[5,3]] | |
| 3 | 1 | = [[34,21],[21,13]] | R = R·B | [[377,233],[233,144]] |
So , and . Three multiplications into R, four squarings of B (the last one is wasted; a careful implementation skips it). Twelve naive multiplications became seven, and the gap grows exponentially: for it is 60 squarings plus 24 extra products (the number of 1-bits in ), against steps.
flowchart LR
B1["B = M^1"] -->|"square"| B2["B = M^2"]
B2 -->|"square"| B4["B = M^4"]
B4 -->|"square"| B8["B = M^8"]
B1 -->|"bit 0 = 1"| R1["R = M^1"]
B4 -->|"bit 2 = 1"| R5["R = M^5"]
B8 -->|"bit 3 = 1"| R13["R = M^13"]
R1 --> R5 --> R13
With a modulus. When the answer is "mod ", reduce every entry after every multiplication. Since and only depend on and , the reduced result equals the true result reduced. This keeps every number below , so with each product of two entries is below and fits in a signed 64-bit integer.
2. Fibonacci in
Running the code below gives
Two independent methods agree on this value: the matrix power, and fast doubling (which we derive from the matrix in the Correctness section):
Fast doubling uses the same recursion depth but about 3 multiplications per bit instead of 8–16, so it is the method of choice for Fibonacci specifically. Matrix power is the one that generalises.
Small checks that the code also asserts: , , (both methods), and the first 200 values against a plain loop.
3. The companion matrix for any linear recurrence
A linear recurrence of order with constant coefficients is
Keep the last values in a state vector, newest first: . One step must produce :
- the new first entry is the recurrence: row 0 is ;
- every other entry shifts down by one: row has a single 1 in column .
This is the companion matrix of the recurrence. Fibonacci is the case , . Tribonacci () is with a first row of three 1s.
flowchart LR
subgraph before["state before"]
A1["a(n-1)"]
A2["a(n-2)"]
A3["a(n-3)"]
end
subgraph after["state after"]
N0["a(n) = c1 a(n-1) + c2 a(n-2) + c3 a(n-3)"]
N1["a(n-1)"]
N2["a(n-2)"]
end
A1 -->|"c1"| N0
A2 -->|"c2"| N0
A3 -->|"c3"| N0
A1 -->|"copy"| N1
A2 -->|"copy"| N2
The oldest value is used once more (in the new ) and then falls off the end. That is all a companion matrix does: one row computes, the rest shift.
Indexing. If the initial values are , the starting state is . Then , and is the first entry of . Off-by-one errors in this exponent are the single most common bug; always test , and against a loop.
4. Adding a constant term
What about ? The "+5" is not a multiple of any previous term, so the plain companion matrix cannot produce it. The fix: put the constant 1 in the state and carry it along.
State . One step:
Row 0 computes . Row 1 shifts. Row 2 reproduces the 1 forever. With , stepping the vector by hand:
| Step | State before | Row 0: | State after |
|---|---|---|---|
| 1 | (1, 1, 1) | 2 + 3 + 5 = 10 | (10, 1, 1) → |
| 2 | (10, 1, 1) | 20 + 3 + 5 = 28 | (28, 10, 1) → |
| 3 | (28, 10, 1) | 56 + 30 + 5 = 91 | (91, 28, 1) → |
| 4 | (91, 28, 1) | 182 + 84 + 5 = 271 | (271, 91, 1) → |
The sequence continues 820, 2458, 7381, 22141, 66430, 199288, and the code computes , checked against a plain loop for .
The same trick handles other "forcing terms":
| Extra term in the recurrence | Extra state entries | Their update rows |
|---|---|---|
| , | (row: 1 on , 1 on the constant) | |
| , , | ||
| running sum | (row = row of plus a 1 on ) |
Each extra term costs one more dimension, and the time grows with the cube of the dimension.
5. Counting walks of length in a graph
Let be the adjacency matrix of a directed graph: if there is an edge , else 0 (or the number of parallel edges). A walk is a sequence of vertices where each consecutive pair is an edge; vertices may repeat (that is the difference from a simple path).
Claim: is the number of walks of exactly edges from to .
Why: a walk of edges from to is a walk of edges from to some , followed by one edge . Summing over the last-but-one vertex :
which is exactly the matrix product formula. It is the "last step" decomposition from grid DP, with the grid replaced by a graph and the step count as the time axis.
Example graph with 4 vertices:
flowchart LR
v0(("0")) --> v1(("1"))
v0 --> v2(("2"))
v1 --> v2
v1 --> v3(("3"))
v2 --> v0
v2 --> v3
v3 --> v0
Check one entry by hand: — the walks and . And : only . The number of walks from 0 to 3 for is . The total number of walks of length 10 (sum of all entries of ) is 1041. The code checks these against a step-by-step DP, and computes .
Walks, not paths
counts walks that may revisit vertices. Counting simple paths of length is #P-hard in general and needs exponential-state methods such as Bitmask DP. If a problem says "paths" but allows revisits, it means walks.
6. Domino tilings with a transfer matrix
How many ways can you tile a board with dominoes?
Fill the board column by column. When you finish column , some horizontal dominoes stick out into column . Record which of the 3 rows they occupy as a 3-bit profile (bitmask; bit set = row already covered). There are profiles. Let be the number of ways to complete a column that arrives with profile already filled, leaving profile sticking into the next column (using vertical dominoes inside the column and horizontal ones that start here).
flowchart LR
P0["profile 000\n(column empty)"] -->|"3 ways in total"| Q["profiles 001, 100, 111"]
Q -->|"each fixes the next column"| R["next profiles"]
R -->|"after n columns"| F["profile 000 again = full board"]
Building for 3 rows by trying every placement (rows are the bit positions, profile written as an integer 0–7) gives:
| from \ to | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 (000) | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 (001) | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| 2 (010) | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 3 (011) | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 4 (100) | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 5 (101) | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 (110) | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 7 (111) | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Read row 0: an empty column can be filled with a vertical domino in rows 0–1 plus a horizontal one in row 2 (profile 100 = 4), a vertical in rows 1–2 plus a horizontal in row 0 (profile 001 = 1), or three horizontals (profile 111 = 7). Row 7: a fully pre-filled column passes on nothing.
A whole board is a sequence of column steps that starts and ends at profile 0 (nothing sticks into column 0 or out past the last column). So:
That is "walks of length from profile 0 to profile 0" in the graph whose adjacency matrix is — section 5 again.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 0 | 11 | 0 | 41 | 0 | 153 | 571 | |
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 89 | |
| 1 | 1 | 5 | 11 | 36 | 95 | 281 | 781 | 2245 | 18061 |
All three rows were checked against a brute-force backtracking tiler for . The row is Fibonacci () — the 2-row transfer matrix is up to relabelling. The counts are 0 for odd (an odd number of cells) and satisfy for even (checked up to ). The count mod is 558008386.
For a board the transfer matrix is , so one product costs . That is fine up to or 7 with . For larger and moderate , do the column steps directly with Broken Profile DP instead.
Deeper: a closed formula exists
Kasteleyn (1961) and, independently, Temperley and Fisher (1961) found the number of domino tilings of an rectangle:
It is beautiful but useless modulo a prime (cosines are not integers mod ). The transfer matrix gives exact counts mod with integer arithmetic only.
The ladder: brute force → better → optimal
Problem: for up to .
Rung 1: plain recursion
fib(n) = fib(n-1) + fib(n-2). The call tree has about leaves, so the time is with . Already hopeless at .
Rung 2: memoised recursion or a loop
Compute in order, keeping the last two. time, space. Excellent for or so. For it is the 31-year loop.
Rung 3: matrix exponentiation
by repeated squaring: products of 2×2 matrices, each 8 multiplications. Around 1,000 modular multiplications for . Works for any linear recurrence.
Rung 4: fast doubling
The identities and walk down the bits of with about 3 multiplications per bit. Same , a constant factor faster, Fibonacci-specific (it generalises to other order-2 recurrences via Lucas sequences, but the bookkeeping grows).
Side rung: the closed form
Binet's formula is exact over the reals but useless here: floating point loses exactness past in doubles, and it does not work mod unless 5 is a quadratic residue mod (it is not for — and even when it is, you need modular square roots).
| Rung | Method | Time | Space | Why better than the rung above |
|---|---|---|---|---|
| 1 | Plain recursion | stack | Baseline | |
| 2 | Loop / memo | Each computed once | ||
| 3 | Matrix power | , | Exponentially fewer steps; any linear recurrence | |
| 4 | Fast doubling | , ~3 mults/bit | stack or iterative | Smaller constant |
| side | Binet | flops | Wrong for large / modular answers |
For a general order- recurrence the ladder is: loop → matrix → Kitamasa → polynomial-multiplication (FFT/NTT) methods . The last two are covered only in Variations.
Correctness
The Fibonacci matrix identity, by induction
Claim. For every ,
with , , .
Base case . , , , so the right side is . ✔
Inductive step. Assume the claim for . Then
using the recurrence twice. That is the claim for . ∎
(Setting also matches if we define , which the recurrence forces: .)
Two free corollaries.
- Cassini's identity. Determinants multiply, and , so , i.e. . Try : . ✔
- Fast doubling. . Compare the top-right entries: . Compare the top-left: . These are exactly the formulas the fast-doubling code uses, so the two "independent" checks of share the identity but not a single line of code.
Binary exponentiation is correct
Invariant: at the start of every loop iteration, , where is the original exponent and , , are the current values.
- Initially , , : . ✔
- Odd : we set , , . Then . ✔
- Even : , , : . ✔
- At exit , so . The loop runs times because halves each time.
Only associativity was used (to regroup ). This is why the same code works for numbers, matrices mod , boolean matrices, and min-plus matrices — all associative.
The companion matrix is correct
By the construction, for every : row 0 applies the recurrence, rows copy. By induction on , . With , the first entry of is . The constant-term version is the same argument on the enlarged state, where the last row keeps the entry equal to 1 forever.
counts walks
Induction on . : is the number of one-edge walks from to by definition. Step: every -edge walk from to splits uniquely at its second-to-last vertex into a -edge walk and an edge . Different give disjoint groups, so the count is . ∎ The transfer-matrix tiling count is this theorem applied to the profile graph: each tiling corresponds to exactly one profile walk of length (the profiles between columns are determined by the tiling, and conversely each walk of compatible column fillings is a tiling).
Complexity
| Task | Time | Space | Notes |
|---|---|---|---|
| One product | multiply-adds | ||
| by squaring | products | ||
| Fibonacci via matrix | : 8 mults per product | ||
| Fibonacci, fast doubling | recursive | ~3 mults per bit | |
| Linear recurrence, loop | best when | ||
| Walks of length on vertices | all pairs at once | ||
| domino tilings | transfer matrix is | ||
| Kitamasa | advanced |
Best / worst case. The number of products depends on the bits of : squarings plus one product per 1-bit. Best case (one 1-bit); worst case (all 1-bits), about twice as many products. For : 60 bits, 24 of them 1s.
When is it worth it? Compare against . For and : loop , matrix — close. For and : the loop is impossible and the matrix costs multiply-adds per product times ~120 products ≈ — about a second in C++. For the matrix method takes minutes; that is where Kitamasa earns its keep.
Several queries. If you need for many different with the same matrix, precompute for once ( products), then each query is a vector times up to 60 matrices: per query instead of , because matrix-times-vector is .
Implementation
The first group is the core library: matrix product and power mod , Fibonacci by matrix and by fast doubling (cross-checked at ), a generic linear recurrence with a constant term, and walk counting. Every block runs its own tests on this lesson's numbers.
Matrix power, Fibonacci, recurrences, walks
MOD = 1_000_000_007
Matrix = list[list[int]]
def mat_mul(A: Matrix, B: Matrix, mod: int = MOD) -> Matrix:
"""C = A * B mod `mod`. i-t-j loop order walks rows of B contiguously."""
n, m, p = len(A), len(B), len(B[0])
C = [[0] * p for _ in range(n)]
for i in range(n):
Ai, Ci = A[i], C[i]
for t in range(m):
a = Ai[t]
if a == 0:
continue
Bt = B[t]
for j in range(p):
Ci[j] = (Ci[j] + a * Bt[j]) % mod
return C
def identity(n: int) -> Matrix:
return [[1 if i == j else 0 for j in range(n)] for i in range(n)]
def mat_pow(M: Matrix, e: int, mod: int = MOD) -> Matrix:
"""M^e by binary exponentiation. Invariant: R * B^e == M^(original e)."""
R, B = identity(len(M)), [row[:] for row in M]
while e > 0:
if e & 1:
R = mat_mul(R, B, mod)
e >>= 1
if e: # skip the wasted last squaring
B = mat_mul(B, B, mod)
return R
def fib_matrix(n: int, mod: int = MOD) -> int:
return mat_pow([[1, 1], [1, 0]], n, mod)[0][1] # top-right of M^n is F(n)
def fib_doubling(n: int, mod: int = MOD) -> int:
"""Fast doubling, iterative over the bits of n from the top. Keeps (F(m), F(m+1))."""
a, b = 0, 1 # m = 0
for bit in bin(n)[2:]:
c = a * ((2 * b - a) % mod) % mod # F(2m)
d = (a * a + b * b) % mod # F(2m+1)
a, b = (d, (c + d) % mod) if bit == "1" else (c, d)
return a
def linear_recurrence(coeffs: list[int], const: int, init: list[int], n: int, mod: int = MOD) -> int:
"""a(n) = coeffs[0]*a(n-1) + ... + coeffs[k-1]*a(n-k) + const, with a(0..k-1) = init."""
k = len(coeffs)
if n < k:
return init[n] % mod
size = k + 1 # last slot carries the constant 1
T = [[0] * size for _ in range(size)]
T[0][:k] = [c % mod for c in coeffs]
T[0][k] = const % mod
for i in range(1, k):
T[i][i - 1] = 1 # shift rows
T[k][k] = 1 # 1 -> 1
state = [init[k - 1 - i] % mod for i in range(k)] + [1] # (a(k-1), ..., a(0), 1)
P = mat_pow(T, n - k + 1, mod)
return sum(P[0][j] * state[j] for j in range(size)) % mod
def count_walks(adj: Matrix, k: int, mod: int = MOD) -> Matrix:
"""Entry (i, j) = number of walks with exactly k edges from i to j (mod `mod`)."""
return mat_pow(adj, k, mod)
if __name__ == "__main__":
# Fibonacci: two independent methods, small and huge n
f = [0, 1]
for _ in range(200):
f.append(f[-1] + f[-2])
for n in range(200):
assert fib_matrix(n) == fib_doubling(n) == f[n] % MOD
assert fib_matrix(10) == 55
assert fib_matrix(13, mod=10**9) == 233
assert mat_pow([[1, 1], [1, 0]], 13, mod=10**9) == [[377, 233], [233, 144]]
assert fib_matrix(50) == fib_doubling(50) == 586268941
assert fib_matrix(90) == fib_doubling(90) == 210345902
assert fib_matrix(10**18) == fib_doubling(10**18) == 209783453
# a(n) = 2a(n-1) + 3a(n-2) + 5, a(0) = a(1) = 1
seq = [1, 1]
for _ in range(2, 1001):
seq.append((2 * seq[-1] + 3 * seq[-2] + 5) % MOD)
for n in range(1001):
assert linear_recurrence([2, 3], 5, [1, 1], n) == seq[n]
assert seq[:12] == [1, 1, 10, 28, 91, 271, 820, 2458, 7381, 22141, 66430, 199288]
assert linear_recurrence([2, 3], 5, [1, 1], 10**18) == 527128770
# Tribonacci (no constant): T(0..2) = 0, 1, 1
assert linear_recurrence([1, 1, 1], 0, [0, 1, 1], 4) == 4
assert linear_recurrence([1, 1, 1], 0, [0, 1, 1], 25) == 1389537
# walks in the lesson's 4-vertex graph, checked against a step-by-step DP
A = [[0, 1, 1, 0], [0, 0, 1, 1], [1, 0, 0, 1], [1, 0, 0, 0]]
assert count_walks(A, 2) == [[1, 0, 1, 2], [2, 0, 0, 1], [1, 1, 1, 0], [0, 1, 1, 0]]
assert [count_walks(A, k)[0][3] for k in range(1, 6)] == [0, 2, 1, 2, 7]
assert sum(map(sum, count_walks(A, 10))) == 1041
ways = [1, 0, 0, 0] # walks from vertex 0, one step at a time
for k in range(1, 30):
ways = [sum(ways[t] * A[t][j] for t in range(4)) for j in range(4)]
assert ways == count_walks(A, k, mod=10**30)[0]
assert count_walks(A, 10**18)[0][3] == 775596649
print("all matrix tests passed")
public class MatrixPower {
static final long MOD = 1_000_000_007L;
/** C = A * B mod MOD. Entries are < MOD < 2^30, so each product is < 2^60: fits in long. */
static long[][] mul(long[][] A, long[][] B) {
int n = A.length, m = B.length, p = B[0].length;
long[][] C = new long[n][p];
for (int i = 0; i < n; i++)
for (int t = 0; t < m; t++) {
long a = A[i][t];
if (a == 0) continue;
for (int j = 0; j < p; j++)
C[i][j] = (C[i][j] + a * B[t][j]) % MOD;
}
return C;
}
static long[][] identity(int n) {
long[][] I = new long[n][n];
for (int i = 0; i < n; i++) I[i][i] = 1;
return I;
}
/** M^e by binary exponentiation; e is a long so 10^18 works. */
static long[][] pow(long[][] M, long e) {
long[][] R = identity(M.length), B = M;
while (e > 0) {
if ((e & 1) == 1) R = mul(R, B);
e >>= 1;
if (e > 0) B = mul(B, B);
}
return R;
}
static long fibMatrix(long n) {
return pow(new long[][]{{1, 1}, {1, 0}}, n)[0][1];
}
/** Fast doubling from the top bit down; keeps (F(m), F(m+1)). */
static long fibDoubling(long n) {
long a = 0, b = 1;
for (int bit = 63 - Long.numberOfLeadingZeros(Math.max(n, 1)); bit >= 0; bit--) {
long c = a * ((2 * b - a + MOD) % MOD) % MOD; // F(2m)
long d = (a * a + b * b) % MOD; // F(2m+1)
if (((n >> bit) & 1) == 1) { a = d; b = (c + d) % MOD; }
else { a = c; b = d; }
}
return n == 0 ? 0 : a;
}
/** a(n) = sum coeffs[i] * a(n-1-i) + c, with a(0..k-1) = init. */
static long linearRecurrence(long[] coeffs, long c, long[] init, long n) {
int k = coeffs.length;
if (n < k) return init[(int) n] % MOD;
int size = k + 1;
long[][] T = new long[size][size];
for (int j = 0; j < k; j++) T[0][j] = coeffs[j] % MOD;
T[0][k] = c % MOD;
for (int i = 1; i < k; i++) T[i][i - 1] = 1;
T[k][k] = 1;
long[] state = new long[size];
for (int i = 0; i < k; i++) state[i] = init[k - 1 - i] % MOD;
state[k] = 1;
long[][] P = pow(T, n - k + 1);
long ans = 0;
for (int j = 0; j < size; j++) ans = (ans + P[0][j] * state[j]) % MOD;
return ans;
}
public static void main(String[] args) {
long[] f = new long[200];
f[1] = 1;
for (int i = 2; i < 200; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
for (int n = 0; n < 200; n++)
check(fibMatrix(n) == f[n] && fibDoubling(n) == f[n]);
check(fibMatrix(10) == 55);
check(fibMatrix(50) == 586268941L && fibDoubling(50) == 586268941L);
check(fibMatrix(1_000_000_000_000_000_000L) == 209783453L);
check(fibDoubling(1_000_000_000_000_000_000L) == 209783453L);
long[] seq = new long[1001];
seq[0] = 1; seq[1] = 1;
for (int i = 2; i <= 1000; i++) seq[i] = (2 * seq[i - 1] + 3 * seq[i - 2] + 5) % MOD;
for (int n = 0; n <= 1000; n++)
check(linearRecurrence(new long[]{2, 3}, 5, new long[]{1, 1}, n) == seq[n]);
check(linearRecurrence(new long[]{2, 3}, 5, new long[]{1, 1}, 1_000_000_000_000_000_000L) == 527128770L);
check(linearRecurrence(new long[]{1, 1, 1}, 0, new long[]{0, 1, 1}, 25) == 1389537);
long[][] A = {{0, 1, 1, 0}, {0, 0, 1, 1}, {1, 0, 0, 1}, {1, 0, 0, 0}};
long[] want = {0, 2, 1, 2, 7};
for (int k = 1; k <= 5; k++) check(pow(A, k)[0][3] == want[k - 1]);
long total = 0;
for (long[] row : pow(A, 10)) for (long v : row) total += v;
check(total == 1041);
check(pow(A, 1_000_000_000_000_000_000L)[0][3] == 775596649L);
System.out.println("all matrix tests passed");
}
static void check(boolean ok) {
if (!ok) throw new AssertionError("test failed");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;
using u64 = uint64_t;
using Matrix = vector<vector<u64>>;
const u64 MOD = 1'000'000'007ULL;
// C = A * B mod MOD. Entries < 2^30, so a product < 2^60 fits in 64 bits.
Matrix mul(const Matrix& A, const Matrix& B) {
size_t n = A.size(), m = B.size(), p = B[0].size();
Matrix C(n, vector<u64>(p, 0));
for (size_t i = 0; i < n; i++)
for (size_t t = 0; t < m; t++) {
u64 a = A[i][t];
if (a == 0) continue;
for (size_t j = 0; j < p; j++) C[i][j] = (C[i][j] + a * B[t][j]) % MOD;
}
return C;
}
Matrix identity(size_t n) {
Matrix I(n, vector<u64>(n, 0));
for (size_t i = 0; i < n; i++) I[i][i] = 1;
return I;
}
Matrix matPow(Matrix B, u64 e) {
Matrix R = identity(B.size());
while (e > 0) {
if (e & 1) R = mul(R, B);
e >>= 1;
if (e) B = mul(B, B);
}
return R;
}
u64 fibMatrix(u64 n) { return matPow({{1, 1}, {1, 0}}, n)[0][1]; }
// Fast doubling from the top bit down; keeps (F(m), F(m+1)).
u64 fibDoubling(u64 n) {
u64 a = 0, b = 1;
for (int bit = 63; bit >= 0; bit--) {
u64 c = a * ((2 * b + MOD - a) % MOD) % MOD; // F(2m)
u64 d = (a * a + b * b) % MOD; // F(2m+1)
if ((n >> bit) & 1) { a = d; b = (c + d) % MOD; }
else { a = c; b = d; }
}
return a;
}
// a(n) = sum coeffs[i] * a(n-1-i) + c, with a(0..k-1) = init.
u64 linearRecurrence(const vector<u64>& coeffs, u64 c, const vector<u64>& init, u64 n) {
size_t k = coeffs.size();
if (n < k) return init[n] % MOD;
size_t size = k + 1;
Matrix T(size, vector<u64>(size, 0));
for (size_t j = 0; j < k; j++) T[0][j] = coeffs[j] % MOD;
T[0][k] = c % MOD;
for (size_t i = 1; i < k; i++) T[i][i - 1] = 1;
T[k][k] = 1;
vector<u64> state(size);
for (size_t i = 0; i < k; i++) state[i] = init[k - 1 - i] % MOD;
state[k] = 1;
Matrix P = matPow(T, n - k + 1);
u64 ans = 0;
for (size_t j = 0; j < size; j++) ans = (ans + P[0][j] * state[j]) % MOD;
return ans;
}
int main() {
vector<u64> f(200);
f[0] = 0; f[1] = 1;
for (int i = 2; i < 200; i++) f[i] = (f[i - 1] + f[i - 2]) % MOD;
for (u64 n = 0; n < 200; n++) assert(fibMatrix(n) == f[n] && fibDoubling(n) == f[n]);
assert(fibMatrix(10) == 55);
assert(fibMatrix(50) == 586268941ULL && fibDoubling(50) == 586268941ULL);
const u64 BIG = 1'000'000'000'000'000'000ULL;
assert(fibMatrix(BIG) == 209783453ULL && fibDoubling(BIG) == 209783453ULL);
vector<u64> seq(1001);
seq[0] = seq[1] = 1;
for (int i = 2; i <= 1000; i++) seq[i] = (2 * seq[i - 1] + 3 * seq[i - 2] + 5) % MOD;
for (u64 n = 0; n <= 1000; n++) assert(linearRecurrence({2, 3}, 5, {1, 1}, n) == seq[n]);
assert(linearRecurrence({2, 3}, 5, {1, 1}, BIG) == 527128770ULL);
assert(linearRecurrence({1, 1, 1}, 0, {0, 1, 1}, 25) == 1389537ULL);
Matrix A = {{0, 1, 1, 0}, {0, 0, 1, 1}, {1, 0, 0, 1}, {1, 0, 0, 0}};
u64 want[] = {0, 2, 1, 2, 7};
for (int k = 1; k <= 5; k++) assert(matPow(A, k)[0][3] == want[k - 1]);
u64 total = 0;
for (auto& row : matPow(A, 10)) for (u64 v : row) total += v;
assert(total == 1041);
assert(matPow(A, BIG)[0][3] == 775596649ULL);
cout << "all matrix tests passed\n";
return 0;
}
const MOD = 1_000_000_007;
type Matrix = number[][];
// a*b mod m without losing precision: a, b < 2^30 but a*b can reach 2^60 > 2^53.
// Split b into 16-bit halves so every intermediate stays below 2^47.
function mulMod(a: number, b: number, m: number = MOD): number {
const hi = Math.floor(b / 65536), lo = b % 65536;
return (((a * hi) % m) * 65536 + a * lo) % m;
}
function mul(A: Matrix, B: Matrix): Matrix {
const n = A.length, m = B.length, p = B[0].length;
const C: Matrix = Array.from({ length: n }, () => new Array<number>(p).fill(0));
for (let i = 0; i < n; i++)
for (let t = 0; t < m; t++) {
const a = A[i][t];
if (a === 0) continue;
for (let j = 0; j < p; j++) C[i][j] = (C[i][j] + mulMod(a, B[t][j])) % MOD;
}
return C;
}
function identity(n: number): Matrix {
return Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => (i === j ? 1 : 0)));
}
// The exponent is a bigint so that 10^18 is represented exactly.
function matPow(M: Matrix, e: bigint): Matrix {
let R = identity(M.length), B = M;
while (e > 0n) {
if (e & 1n) R = mul(R, B);
e >>= 1n;
if (e > 0n) B = mul(B, B);
}
return R;
}
function fibMatrix(n: bigint): number {
return matPow([[1, 1], [1, 0]], n)[0][1];
}
function fibDoubling(n: bigint): number {
let a = 0, b = 1; // (F(m), F(m+1)), m = 0
for (const bit of n.toString(2)) {
const c = mulMod(a, (2 * b - a + MOD) % MOD); // F(2m)
const d = (mulMod(a, a) + mulMod(b, b)) % MOD; // F(2m+1)
if (bit === "1") { a = d; b = (c + d) % MOD; } else { a = c; b = d; }
}
return a;
}
function linearRecurrence(coeffs: number[], c: number, init: number[], n: bigint): number {
const k = coeffs.length;
if (n < BigInt(k)) return init[Number(n)] % MOD;
const size = k + 1;
const T: Matrix = Array.from({ length: size }, () => new Array<number>(size).fill(0));
for (let j = 0; j < k; j++) T[0][j] = coeffs[j] % MOD;
T[0][k] = c % MOD;
for (let i = 1; i < k; i++) T[i][i - 1] = 1;
T[k][k] = 1;
const state: number[] = [];
for (let i = 0; i < k; i++) state.push(init[k - 1 - i] % MOD);
state.push(1);
const P = matPow(T, n - BigInt(k) + 1n);
let ans = 0;
for (let j = 0; j < size; j++) ans = (ans + mulMod(P[0][j], state[j])) % MOD;
return ans;
}
function assert(ok: boolean, msg = "test failed"): void {
if (!ok) throw new Error(msg);
}
const fibs = [0, 1];
for (let i = 2; i < 200; i++) fibs.push((fibs[i - 1] + fibs[i - 2]) % MOD);
for (let n = 0; n < 200; n++) assert(fibMatrix(BigInt(n)) === fibs[n] && fibDoubling(BigInt(n)) === fibs[n]);
assert(fibMatrix(10n) === 55);
assert(fibMatrix(50n) === 586268941 && fibDoubling(50n) === 586268941);
const BIG = 10n ** 18n;
assert(fibMatrix(BIG) === 209783453 && fibDoubling(BIG) === 209783453);
const seq = [1, 1];
for (let i = 2; i <= 1000; i++) seq.push((2 * seq[i - 1] + 3 * seq[i - 2] + 5) % MOD);
for (let n = 0; n <= 1000; n++) assert(linearRecurrence([2, 3], 5, [1, 1], BigInt(n)) === seq[n]);
assert(linearRecurrence([2, 3], 5, [1, 1], BIG) === 527128770);
assert(linearRecurrence([1, 1, 1], 0, [0, 1, 1], 25n) === 1389537);
const A: Matrix = [[0, 1, 1, 0], [0, 0, 1, 1], [1, 0, 0, 1], [1, 0, 0, 0]];
[0, 2, 1, 2, 7].forEach((w, i) => assert(matPow(A, BigInt(i + 1))[0][3] === w));
assert(matPow(A, 10n).flat().reduce((s, v) => s + v, 0) === 1041);
assert(matPow(A, BIG)[0][3] === 775596649);
console.log("all matrix tests passed");
Notes on the four versions. Python integers never overflow, so the only reason to reduce is speed. Java and C++ rely on so that one product fits in 64 bits; reducing after every multiply-add keeps the running sum below . TypeScript's number is a double, exact only up to , so a product of two residues can silently lose its low bits — mulMod splits one factor into 16-bit halves. (Using bigint throughout is the simpler alternative; it is roughly an order of magnitude slower.)
Transfer matrix: domino tilings
The transfer matrix is built by a small recursion over the rows of one column, then raised to the -th power with the same mat_pow.
MOD = 1_000_000_007
def mat_mul(A, B, mod=MOD):
n, m, p = len(A), len(B), len(B[0])
C = [[0] * p for _ in range(n)]
for i in range(n):
for t in range(m):
if A[i][t]:
a, Bt, Ci = A[i][t], B[t], C[i]
for j in range(p):
Ci[j] = (Ci[j] + a * Bt[j]) % mod
return C
def mat_pow(M, e, mod=MOD):
R = [[int(i == j) for j in range(len(M))] for i in range(len(M))]
while e:
if e & 1:
R = mat_mul(R, M, mod)
e >>= 1
if e:
M = mat_mul(M, M, mod)
return R
def transfer_matrix(k: int) -> list[list[int]]:
"""T[p][q] = ways to fill one column of height k that arrives with rows `p` already
covered and leaves rows `q` covered in the next column (by horizontal dominoes)."""
S = 1 << k
T = [[0] * S for _ in range(S)]
def fill(row: int, cur: int, nxt: int, src: int) -> None:
if row == k:
T[src][nxt] += 1
return
if cur >> row & 1: # already covered
fill(row + 1, cur, nxt, src)
return
fill(row + 1, cur, nxt | 1 << row, src) # horizontal domino
if row + 1 < k and not cur >> (row + 1) & 1: # vertical domino
fill(row + 2, cur, nxt, src)
for p in range(S):
fill(0, p, 0, p)
return T
def domino_tilings(k: int, n: int, mod: int = MOD) -> int:
return mat_pow(transfer_matrix(k), n, mod)[0][0]
def brute_tilings(k: int, n: int) -> int:
"""Backtracking: cover the first empty cell (column-major) with a domino."""
g = [[False] * n for _ in range(k)]
def go(i: int) -> int:
if i == k * n:
return 1
r, c = i % k, i // k
if g[r][c]:
return go(i + 1)
total = 0
if c + 1 < n and not g[r][c + 1]:
g[r][c] = g[r][c + 1] = True
total += go(i + 1)
g[r][c] = g[r][c + 1] = False
if r + 1 < k and not g[r + 1][c]:
g[r][c] = g[r + 1][c] = True
total += go(i + 1)
g[r][c] = g[r + 1][c] = False
return total
return go(0)
if __name__ == "__main__":
assert transfer_matrix(3)[0] == [0, 1, 0, 0, 1, 0, 0, 1]
for k in (1, 2, 3, 4):
for n in range(0, 9):
assert domino_tilings(k, n) == brute_tilings(k, n), (k, n)
assert [domino_tilings(3, n) for n in range(0, 11, 2)] == [1, 3, 11, 41, 153, 571]
assert domino_tilings(2, 10) == 89
assert domino_tilings(4, 10) == 18061
assert domino_tilings(3, 10**18) == 558008386
print("all tiling tests passed")
public class DominoTransfer {
static final long MOD = 1_000_000_007L;
static long[][] mul(long[][] A, long[][] B) {
int n = A.length;
long[][] C = new long[n][n];
for (int i = 0; i < n; i++)
for (int t = 0; t < n; t++) {
if (A[i][t] == 0) continue;
for (int j = 0; j < n; j++) C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
static long[][] pow(long[][] B, long e) {
int n = B.length;
long[][] R = new long[n][n];
for (int i = 0; i < n; i++) R[i][i] = 1;
while (e > 0) {
if ((e & 1) == 1) R = mul(R, B);
e >>= 1;
if (e > 0) B = mul(B, B);
}
return R;
}
static int K;
static long[][] T;
static void fill(int row, int cur, int nxt, int src) {
if (row == K) { T[src][nxt]++; return; }
if (((cur >> row) & 1) == 1) { fill(row + 1, cur, nxt, src); return; }
fill(row + 1, cur, nxt | (1 << row), src); // horizontal
if (row + 1 < K && ((cur >> (row + 1)) & 1) == 0) fill(row + 2, cur, nxt, src); // vertical
}
static long[][] transferMatrix(int k) {
K = k;
T = new long[1 << k][1 << k];
for (int p = 0; p < (1 << k); p++) fill(0, p, 0, p);
return T;
}
static long dominoTilings(int k, long n) {
return pow(transferMatrix(k), n)[0][0];
}
public static void main(String[] args) {
long[] three = {1, 0, 3, 0, 11, 0, 41, 0, 153};
for (int n = 0; n < three.length; n++) check(dominoTilings(3, n) == three[n]);
check(dominoTilings(3, 10) == 571);
check(dominoTilings(2, 10) == 89);
check(dominoTilings(4, 10) == 18061);
check(dominoTilings(3, 1_000_000_000_000_000_000L) == 558008386L);
System.out.println("all tiling tests passed");
}
static void check(boolean ok) {
if (!ok) throw new AssertionError("test failed");
}
}
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;
using u64 = uint64_t;
using Matrix = vector<vector<u64>>;
const u64 MOD = 1'000'000'007ULL;
Matrix mul(const Matrix& A, const Matrix& B) {
size_t n = A.size();
Matrix C(n, vector<u64>(n, 0));
for (size_t i = 0; i < n; i++)
for (size_t t = 0; t < n; t++) {
if (!A[i][t]) continue;
for (size_t j = 0; j < n; j++) C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
}
return C;
}
Matrix matPow(Matrix B, u64 e) {
size_t n = B.size();
Matrix R(n, vector<u64>(n, 0));
for (size_t i = 0; i < n; i++) R[i][i] = 1;
while (e) {
if (e & 1) R = mul(R, B);
e >>= 1;
if (e) B = mul(B, B);
}
return R;
}
Matrix transferMatrix(int k) {
int S = 1 << k;
Matrix T(S, vector<u64>(S, 0));
function<void(int, int, int, int)> fill = [&](int row, int cur, int nxt, int src) {
if (row == k) { T[src][nxt]++; return; }
if ((cur >> row) & 1) { fill(row + 1, cur, nxt, src); return; }
fill(row + 1, cur, nxt | (1 << row), src); // horizontal
if (row + 1 < k && !((cur >> (row + 1)) & 1)) fill(row + 2, cur, nxt, src); // vertical
};
for (int p = 0; p < S; p++) fill(0, p, 0, p);
return T;
}
u64 dominoTilings(int k, u64 n) { return matPow(transferMatrix(k), n)[0][0]; }
int main() {
u64 three[] = {1, 0, 3, 0, 11, 0, 41, 0, 153};
for (int n = 0; n < 9; n++) assert(dominoTilings(3, n) == three[n]);
assert(dominoTilings(3, 10) == 571);
assert(dominoTilings(2, 10) == 89);
assert(dominoTilings(4, 10) == 18061);
assert(dominoTilings(3, 1'000'000'000'000'000'000ULL) == 558008386ULL);
cout << "all tiling tests passed\n";
return 0;
}
const P = 1_000_000_007;
type Mat = number[][];
function mulMod(a: number, b: number): number {
return (((a * Math.floor(b / 65536)) % P) * 65536 + a * (b % 65536)) % P;
}
function mul(A: Mat, B: Mat): Mat {
const n = A.length;
const C: Mat = Array.from({ length: n }, () => new Array<number>(n).fill(0));
for (let i = 0; i < n; i++)
for (let t = 0; t < n; t++) {
if (A[i][t] === 0) continue;
for (let j = 0; j < n; j++) C[i][j] = (C[i][j] + mulMod(A[i][t], B[t][j])) % P;
}
return C;
}
function matPow(B: Mat, e: bigint): Mat {
let R: Mat = B.map((row, i) => row.map((_, j) => (i === j ? 1 : 0)));
while (e > 0n) {
if (e & 1n) R = mul(R, B);
e >>= 1n;
if (e > 0n) B = mul(B, B);
}
return R;
}
function transferMatrix(k: number): Mat {
const S = 1 << k;
const T: Mat = Array.from({ length: S }, () => new Array<number>(S).fill(0));
const fill = (row: number, cur: number, nxt: number, src: number): void => {
if (row === k) { T[src][nxt]++; return; }
if ((cur >> row) & 1) { fill(row + 1, cur, nxt, src); return; }
fill(row + 1, cur, nxt | (1 << row), src); // horizontal
if (row + 1 < k && !((cur >> (row + 1)) & 1)) fill(row + 2, cur, nxt, src); // vertical
};
for (let p = 0; p < S; p++) fill(0, p, 0, p);
return T;
}
function dominoTilings(k: number, n: bigint): number {
return matPow(transferMatrix(k), n)[0][0];
}
function check(ok: boolean): void {
if (!ok) throw new Error("test failed");
}
[1, 0, 3, 0, 11, 0, 41, 0, 153].forEach((w, n) => check(dominoTilings(3, BigInt(n)) === w));
check(dominoTilings(3, 10n) === 571);
check(dominoTilings(2, 10n) === 89);
check(dominoTilings(4, 10n) === 18061);
check(dominoTilings(3, 10n ** 18n) === 558008386);
console.log("all tiling tests passed");
Real-world uses
- Jump-ahead in random number generators. A linear congruential generator is an affine step, i.e. a 2×2 matrix on — exactly the "constant term" trick. Raising it to the power skips outputs in , so parallel workers can take disjoint slices of one stream. Forrest Brown described this for Monte Carlo codes ("Random Number Generation with Arbitrary Strides", 1994), and NumPy's
PCG64bit generator exposes it asadvance(delta)andjumped()(NumPy documentation,numpy.random.PCG64). For -linear generators like the Mersenne Twister, jump-ahead uses the same idea with polynomial arithmetic (Haramoto, Matsumoto, Nishimura, Panneton, L'Ecuyer, "Efficient Jump Ahead for -Linear Random Number Generators", INFORMS Journal on Computing, 2008); thexoshirofamily ships precomputedjump()functions (Blackman and Vigna). - Markov chains. If is a transition matrix, gives the -step transition probabilities (the Chapman–Kolmogorov equations). Absorption probabilities in games, queueing models and reliability analysis are read off powers of . (PageRank's power iteration multiplies a vector by repeatedly — the same "same linear step, many times" structure — but it iterates to convergence rather than exponentiating by squaring.)
- Transfer matrices in statistical physics. The 1-D Ising model's partition function is for a 2×2 transfer matrix (Kramers and Wannier, 1941); strips of 2-D lattices use larger transfer matrices exactly like our domino profiles. Counting dimer coverings (domino tilings) is the physics "dimer problem".
- Graph reachability and closure. Repeated squaring of the boolean matrix computes reachability within steps after squarings, which is one classic route to transitive closure in — and, with fast matrix multiplication, to sub-cubic algorithms (Fischer and Meyer, 1971). The min-plus version of gives shortest walks with exactly edges.
- Linear-feedback shift registers. LFSRs in CRC hardware, scramblers and stream ciphers are linear recurrences over . Their companion matrix is the reason why "advance the register steps" and "find the period" are linear-algebra questions, and why Berlekamp–Massey can recover an LFSR from output bits (Massey, 1969) — a classic cryptanalytic attack on bare LFSR ciphers.
- Computer graphics and robotics. Repeating the same affine transform times (a rotation step in an animation, a robot arm segment chain) is a matrix power in homogeneous coordinates — the constant-term trick again, with the "1" coordinate.
Pitfalls & edge cases
- Overflow in the product. With , entries are below and one product is below — fine in signed 64-bit. Summing of them without reducing can overflow: products of nearly exceed . Reduce after every multiply-add, or accumulate in unsigned 64-bit and reduce every 8 terms if you are tuning.
- Moduli near or . Then does not fit in 64 bits at all. In C++ use
(unsigned __int128)a * b % m(GCC/Clang). In Java useMath.multiplyHigh(a, b)(Java 9+) to get the high 64 bits and reduce by hand, orBigInteger. In TypeScript/JavaScript useBigInt. Python is unaffected.
// C++ (GCC/Clang): safe a*b mod m for any 64-bit m
#include <cstdint>
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t m) {
return (unsigned __int128)a * b % m;
}
- JavaScript numbers. Doubles are exact only to . A product of two residues mod reaches , so
a * b % MODsilently returns a wrong value. Split one factor (as inmulMod) or useBigInt. This bug passes small tests and fails large ones. - Exponent type. needs a 64-bit integer (
long,u64,bigint). In TypeScript,10 ** 18as anumberis exact only by luck; use10n ** 18n. - Off-by-one in the exponent. With state starting at , the power is . Test against a loop, always.
- . , so the code must return the identity, not . Fast doubling must return .
- Negative coefficients. A recurrence like has a . Store it as (or normalise with
((x % p) + p) % p); in C++ and Java,%of a negative number is negative. - Wrong multiplication order. For a single matrix the order does not matter, but when steps alternate (e.g. an "odd step" matrix and "even step" matrix ), the combined step is (apply first, then ), and you exponentiate , not .
- Walks vs paths. counts walks with repeated vertices. Self-loops count as walks too.
- Reading the wrong entry. For , is the top-right (or bottom-left) entry, not the top-left ().
- Too-large . A transfer matrix for is : one product is operations and you need ~120. Switch to broken-profile DP, or reduce states with symmetry.
- Recurrence is not linear. , , or anything with
maxcannot be a matrix over ordinary . Themax/mincases may still work in the max-plus/min-plus semiring if the step is "max of (value + constant)".
Variations
Min-plus (tropical) matrix power. Replace with and with : . This is still associative, so binary exponentiation works, and is the cheapest walk with exactly edges. Max-plus gives the most valuable walk. Floyd–Warshall-style shortest paths are the "closure" of this semiring (Shortest Paths).
Boolean matrices. Replace with (OR, AND). tells you whether a walk of length exists. With bitsets, a product of boolean matrices costs word operations.
Sums of a linear recurrence. To get , add to the state. For Fibonacci there is also the identity .
Sum of matrix powers . Use the block matrix , whose powers carry the partial sums in the top-right block; or recursive halving .
Time-dependent but periodic steps. If the step matrix cycles through , combine one period into , exponentiate by and finish the remainder by hand.
Kitamasa's method (advanced, not covered in depth). For an order- recurrence, is a fixed linear combination of . Kitamasa finds that combination by computing the characteristic polynomial with binary exponentiation on polynomials: with schoolbook multiplication, or with FFT/NTT (see FFT & NTT). It wins once is in the hundreds.
Berlekamp–Massey (advanced, not covered in depth). Given the first terms of a sequence over a field (e.g. mod a prime) that satisfies some linear recurrence of order at most , Berlekamp–Massey (Berlekamp 1968, Massey 1969) finds the shortest such recurrence in . Competitive programmers use it as a black box: compute the first few hundred terms of a messy DP by brute force, recover the recurrence, then jump with Kitamasa. It only works if the sequence really is linearly recurrent, which is true whenever it comes from a fixed-size linear DP (by the Cayley–Hamilton theorem). See cp-algorithms or the Linear Algebra lesson when it is published.
Faster matrix multiplication. Strassen's algorithm () and later improvements exist, but for the small used here (2 to 100) the cubic loop with good memory order wins in practice.
Characteristic-polynomial closed forms. Every linear recurrence has a closed form via the roots of its characteristic polynomial (like Binet for Fibonacci). Useful for asymptotics (), rarely for exact modular answers.
Practice ladder
Easy to hard. Hints for all; full solutions for the key ones. The solution code was run against brute-force loops for small inputs.
1. Fibonacci Number (LeetCode 509) — The -th Fibonacci number for small . Teaches the base cases you must get right before scaling up.
Hint
A loop is enough here. Use it as a test oracle for your matrix code: fib_matrix(n) == loop(n) for .
2. Climbing Stairs (LeetCode 70) — Ways to climb stairs with steps of 1 or 2. Teaches recognising Fibonacci in disguise.
Hint
ways(n) = ways(n-1) + ways(n-2), ways(0) = ways(1) = 1, so ways(n) = F(n+1).
3. N-th Tribonacci Number (LeetCode 1137) — Order-3 recurrence. Teaches building a 3×3 companion matrix.
Hint
Companion matrix with first row [1, 1, 1], state (T(n-1), T(n-2), T(n-3)). For the answer is 1389537.
4. Fibonacci Numbers (CSES 1722) — for up to . Teaches the whole technique on the smallest matrix.
Solution
MOD = 10**9 + 7
def fib(n):
a, b = 0, 1 # (F(m), F(m+1)), fast doubling
for bit in bin(n)[2:]:
c = a * ((2 * b - a) % MOD) % MOD
d = (a * a + b * b) % MOD
a, b = (d, (c + d) % MOD) if bit == "1" else (c, d)
return a
assert fib(10) == 55
assert fib(10**18) == 209783453
5. Throwing Dice (CSES 1096) — Number of ordered dice-throw sequences summing to , up to . Teaches a 6×6 companion matrix.
Solution
, , . With state starting at , is entry of .
MOD = 10**9 + 7
def mat_mul(A, B):
n = len(A)
return [[sum(A[i][t] * B[t][j] for t in range(n)) % MOD for j in range(n)] for i in range(n)]
def mat_pow(M, e):
R = [[int(i == j) for j in range(len(M))] for i in range(len(M))]
while e:
if e & 1:
R = mat_mul(R, M)
M = mat_mul(M, M)
e >>= 1
return R
def dice(n):
C = [[1] * 6] + [[int(j == i - 1) for j in range(6)] for i in range(1, 6)]
return mat_pow(C, n)[0][0]
f = [1] + [0] * 30
for i in range(1, 31):
f[i] = sum(f[i - j] for j in range(1, 7) if i - j >= 0)
assert all(dice(n) == f[n] for n in range(31))
assert dice(3) == 4 and dice(10) == 492
assert dice(10**18) == 106021903
6. Count Vowels Permutation (LeetCode 1220) — Strings of length over vowels with "which vowel may follow which" rules. Teaches that a "follows" table is an adjacency matrix.
Hint
Build the 5×5 "may follow" matrix . The answer is the sum of all entries of (walks of edges = strings of letters).
7. Knight Dialer (LeetCode 935) — Phone numbers of length dialled by knight moves. Same idea on a 10-vertex graph.
Hint
The adjacency matrix of knight jumps on the keypad; the answer is the sum of entries of . Digit 5 has no moves (it only counts for ).
8. Number of Ways to Paint N × 3 Grid (LeetCode 1411) — Color an grid with 3 colors, no equal neighbours. Teaches compressing 12 row patterns into 2 classes.
Solution
Each valid row is either an "ABA" pattern (6 of them) or an "ABC" pattern (6 of them). Below an ABA row fit 3 ABA and 2 ABC rows; below an ABC row fit 2 ABA and 2 ABC rows. So — a 2×2 matrix.
MOD = 10**9 + 7
def num_of_ways(n):
def mul(A, B):
return [[(A[i][0] * B[0][j] + A[i][1] * B[1][j]) % MOD for j in range(2)] for i in range(2)]
R, M, e = [[1, 0], [0, 1]], [[3, 2], [2, 2]], n - 1
while e:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
x = (R[0][0] * 6 + R[0][1] * 6) % MOD # ABA rows at level n
y = (R[1][0] * 6 + R[1][1] * 6) % MOD # ABC rows at level n
return (x + y) % MOD
assert [num_of_ways(n) for n in (1, 2, 3, 7)] == [12, 54, 246, 106494]
assert num_of_ways(5000) == 30228214
9. Domino and Tromino Tiling (LeetCode 790) — Tile a board with dominoes and L-trominoes. Teaches profile states with more than one piece shape.
Hint
States: column fully filled, or one cell sticking out (top or bottom). Derive the transitions, or find the known recurrence and exponentiate its companion matrix.
10. Graph Paths I (CSES 1723) — Count routes of exactly flights from city 1 to city (, , repeated flights counted). Teaches with multi-edges.
Hint
= number of flights (there may be several). Answer: . multiply-adds.
11. Walk (AtCoder Educational DP Contest R) — Total number of directed walks of length () in a graph given by an adjacency matrix. Teaches summing all entries of .
Solution
MOD = 10**9 + 7
def mat_mul(A, B):
n = len(A)
C = [[0] * n for _ in range(n)]
for i in range(n):
for t in range(n):
if A[i][t]:
for j in range(n):
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD
return C
def total_walks(adj, K):
n = len(adj)
R = [[int(i == j) for j in range(n)] for i in range(n)]
M = adj
while K:
if K & 1:
R = mat_mul(R, M)
M = mat_mul(M, M)
K >>= 1
return sum(map(sum, R)) % MOD
A = [[0, 1, 1, 0], [0, 0, 1, 1], [1, 0, 0, 1], [1, 0, 0, 0]]
assert total_walks(A, 10) == 1041
12. Graph Paths II (CSES 1724) — The cheapest route from city 1 to city using exactly flights. Teaches min-plus matrix exponentiation.
Solution
Same binary exponentiation, with and identity "0 on the diagonal, elsewhere".
INF = float("inf")
def min_plus(A, B):
n = len(A)
return [[min(A[i][t] + B[t][j] for t in range(n)) for j in range(n)] for i in range(n)]
def cheapest_k_edges(n, edges, k):
A = [[INF] * n for _ in range(n)]
for u, v, w in edges: # 0-indexed, keep the cheapest parallel edge
A[u][v] = min(A[u][v], w)
R = [[0 if i == j else INF for j in range(n)] for i in range(n)]
while k:
if k & 1:
R = min_plus(R, A)
A = min_plus(A, A)
k >>= 1
return -1 if R[0][n - 1] == INF else R[0][n - 1]
def brute(n, edges, k): # layer-by-layer DP over exactly k edges
dist = [0] + [INF] * (n - 1)
for _ in range(k):
nd = [INF] * n
for u, v, w in edges:
nd[v] = min(nd[v], dist[u] + w)
dist = nd
return -1 if dist[n - 1] == INF else dist[n - 1]
E = [(0, 1, 4), (1, 2, 3), (2, 0, 2), (0, 2, 10), (2, 2, 1)]
for k in range(1, 12):
assert cheapest_k_edges(3, E, k) == brute(3, E, k)
assert cheapest_k_edges(3, E, 2) == 7 and cheapest_k_edges(3, E, 4) == 9
13. Student Attendance Record II (LeetCode 552) — Count attendance strings of length with fewer than 2 absences and no 3 consecutive lates. Teaches turning a hand-written state machine into a 6×6 matrix.
Hint
State = (absences so far ∈ {0,1}, current trailing lates ∈ {0,1,2}) — 6 states. Write the transition for each of P, A, L, then the answer is the sum of row 0 of . The intended loop also passes; the matrix is for practice.
14. Plant (Codeforces 185A) — Triangles that split into "upward" and "downward" ones each year; count upward ones after years. Teaches modelling a growth process as a 2×2 matrix.
Hint
Each upward triangle produces 3 upward and 1 downward; each downward produces 1 upward and 3 downward. State (up, down), matrix . Mind .
15. Magic Gems (Codeforces 1117D) — Count configurations where each magic gem is either kept whole or split into units, totalling units (, ). Teaches a sparse order- recurrence and the budget.
Hint
with for . The companion matrix is ; operations — fine in C++, tight in Python.
Common mistakes & interview follow-ups
"Why is it and not ?" Each loop iteration halves the exponent, so there are iterations, each doing at most two products. Mention the invariant .
"Derive the matrix for ." State ; first row ; two shift rows; last row . Interviewers want to see the constant carried in the state.
"Is Binet's formula faster?" It is floating-point operations but loses exactness around in doubles and does not work mod (5 has no square root mod that prime).
"How would you compute many terms ?" Precompute once; each query multiplies a vector by precomputed matrices, per query.
"What about ?" — too slow. Mention Kitamasa () or NTT-based polynomial methods, and Berlekamp–Massey if the recurrence is unknown.
"Count paths of length — simple paths?" If revisits are forbidden, is wrong; that problem is exponential in general.
Mistakes interviewers watch for: returning instead of for ; off-by-one in the exponent; overflow in a * b (especially in JavaScript); forgetting to reduce negative coefficients; reading instead of ; not reducing the exponent's type to 64 bits; using int for .
Quick quiz
1. In the dry run, which powers of get multiplied into , and why those?
Answer
, and , because . The bit for is 0, so is computed (as a stepping stone) but not used in .
2. Write the companion matrix for modulo .
Answer
— the is stored as .
3. In the 4-vertex example graph, why is ?
Answer
The length-2 walks from 0 to 3 are and . Formally, .
4. Why are the domino counts zero for odd , and how does the transfer matrix "know"?
Answer
A board with odd has an odd number of cells, and each domino covers 2. The matrix knows through parity: in one column, the cells already covered ( of them), the new horizontal dominoes ( cells) and the vertical dominoes (2 cells each) add up to 3, so is odd. Every step flips the parity of the number of set bits in the profile, so a walk from profile 0 back to profile 0 must have even length, and for odd .
5. You need with in C++. What do you write?
Answer
(unsigned __int128)a * b % m. A 64-bit product would overflow.
6. What does say about Fibonacci numbers?
Answer
Cassini's identity: .
Further reading / sources
- Donald E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. — §4.6.3 (evaluation of powers; binary method and its history).
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 4 (matrix multiplication, Strassen) and Problem 31-3 on Fibonacci numbers.
- cp-algorithms: Binary Exponentiation, Fibonacci Numbers (fast doubling), and Number of paths of fixed length.
- H. W. Gould, "A History of the Fibonacci Q-Matrix and a Higher-Dimensional Problem", The Fibonacci Quarterly 19(3), 1981.
- P. W. Kasteleyn, "The statistics of dimers on a lattice", Physica 27, 1961; H. N. V. Temperley and M. E. Fisher, "Dimer problem in statistical mechanics — an exact result", Philosophical Magazine 6, 1961.
- Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed. — §4.7 (the transfer-matrix method).
- James L. Massey, "Shift-register synthesis and BCH decoding", IEEE Transactions on Information Theory 15(1), 1969.
- H. Haramoto, M. Matsumoto, T. Nishimura, F. Panneton, P. L'Ecuyer, "Efficient Jump Ahead for -Linear Random Number Generators", INFORMS Journal on Computing 20(3), 2008.
- NumPy documentation,
numpy.random.PCG64(advance,jumped). - AtCoder Educational DP Contest, problem list — problem R is walk counting by matrix power.
Lessons: previous — Game DP · next — DP Optimizations · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Grid & Path DP · Counting DP · Digit DP · Broken Profile DP · Bitmask DP · Shortest Paths · Recursion & Induction · Complexity Analysis · Modular Arithmetic · Linear Algebra.