These are the notes for Competitive Programming episode 29 (matrix exponentiation). Climbing the station footbridge one or two steps at a time gives the Fibonacci recurrence. An original problem, Rangoli Border, asks for the number of ways to tile a border of length n with tiles of length 1, 2 and 3, for n up to 10^18. The plain DP loop is correct on the samples and gets Time Limit Exceeded: 10^18 steps would take about 31 years. The fix: one step of the loop is a fixed linear map, so it is a matrix T times a state vector, n steps are T^n, and because matrix multiplication is associative, episode 21's square-and-multiply computes T^n in about 60 multiplications, starting from the identity matrix. A stress test checks the matrix power against the loop for every n ≤ 2000. Part two, Auto Routes, counts walks of exactly k steps in a graph with the adjacency matrix A^k. Three real bugs close the episode. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hooks
The station footbridge. You run up the stairs taking 1 or 2 steps at a time. Four steps can be climbed in 5 ways: 1111, 112, 121, 211, 22. Your last move was either 1 step or 2, so ways(n) = ways(n − 1) + ways(n − 2): 1, 1, 2, 3, 5, 8, 13, … (the Fibonacci numbers).
A chai recipe card. A tea stall's card says how much milk, water and tea leaves go into the next batch, in fixed amounts. The card is the matrix; today's pot is the state vector. You can combine four uses of the card into one "×4" card first and use it once: that is multiplying the matrix by itself.
Auto routes. Three stops (home, market, college) joined by one-way roads. How many routes use exactly k rides? Counting by "the last road you took" again gives fixed multipliers: a matrix power.
Recurrences and linear recurrences
A recurrence defines each term from earlier terms plus a few starting values (the base cases):
f(n) = f(n−1) + f(n−2), f(0) = f(1) = 1 (Fibonacci-style)
It is linear when every earlier term is only multiplied by a fixed number and the results are added:
| Recurrence | Linear? |
|---|---|
| f(n) = 2·f(n−1) + 3·f(n−2) | yes |
| f(n) = f(n−1) + f(n−2) + 5 | yes, with an extra "always 1" state |
| f(n) = f(n−1) · f(n−2) | no (a product of terms) |
| f(n) = f(n−1) + n | yes, with states for n and 1 |
Problem F · Rangoli Border
(Written for this course, in the style of a Codeforces Div. 2 problem.)
For Diwali you decorate a border of length n with painted tiles of length 1, 2 and 3. Two patterns are different if the tiles come in a different order (1 + 2 differs from 2 + 1). Count the patterns modulo 10^9 + 7.
- Input: one integer n (0 ≤ n ≤ 10^18).
- Output: the number of patterns mod 10^9 + 7.
| Input | Output |
|---|---|
1 |
1 |
4 |
7 |
10 |
274 |
Recurrence. Split by the last tile: ways(n) = ways(n − 1) + ways(n − 2) + ways(n − 3), with ways(0) = 1 (the empty border) and ways of a negative length = 0.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| ways(n) | 1 | 1 | 2 | 4 | 7 | 13 | 24 |
Brute force: the O(n) loop (Time Limit Exceeded)
Keep only the last three values a, b, c and slide the window:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
int main() {
ll n;
cin >> n;
ll a = 1, b = 0, c = 0; // ways(i), ways(i-1), ways(i-2)
for (ll i = 1; i <= n; i++) {
ll next = (a + b + c) % MOD;
c = b; b = a; a = next;
}
cout << a << "\n";
return 0;
}
Real runs: 4 → 7, 10 → 274, 1000000000000000000 → Time Limit Exceeded. 10^18 steps at about 10^9 simple steps per second is 10^9 seconds, about 31 years.
Key observation: one step is a matrix
One step maps the window (a, b, c) to (a + b + c, a, b):
new a = 1·a + 1·b + 1·c
new b = 1·a + 0·b + 0·c
new c = 0·a + 1·b + 0·c
The nine multipliers never change, so one step is the matrix
T = | 1 1 1 |
| 1 0 0 |
| 0 1 0 |
times the state vector. Then state(n) = T · state(n − 1) = T^n · state(0), with state(0) = (ways 0, ways −1, ways −2) = (1, 0, 0). Multiplying by (1, 0, 0) picks the first column, so ways(n) = T^n[0][0].
Matrix multiplication
Entry (i, j) of A · B is row i of A times column j of B, entry by entry, added up:
C[i][j] = Σ_t A[i][t] · B[t][j]
| 1 1 | | 1 1 | | 2 1 |
| 1 0 | · | 1 0 | = | 1 1 |
- Associative: (A · B) · C = A · (B · C). This is what makes squaring work: T^10 = T^8 · T^2, no matter how you group the products.
- Not commutative in general: A · B can differ from B · A (for powers of the same T it doesn't matter).
- Identity matrix I: 1s on the diagonal, 0 elsewhere. I · A = A · I = A. It is "the number 1" of matrices, and T^0 = I.
- Cost: k × k matrices take k³ multiplications per product.
Square and multiply on matrices
Exactly episode 21's loop, with 1 replaced by I and * by mul. For n = 10 = 1010₂:
| bit of 10 | 0 | 1 | 0 | 1 |
|---|---|---|---|---|
| M | T | T² | T⁴ | T⁸ |
| R | I | T² | T² | T¹⁰ |
For n = 10^18 the loop runs about 60 times, so about 120 matrix products.
The accepted solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Mat = vector<vector<ll>>;
const ll MOD = 1e9 + 7;
Mat mul(const Mat& A, const Mat& B) {
int k = A.size();
Mat C(k, vector<ll>(k, 0));
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
for (int t = 0; t < k; t++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
return C;
}
Mat power(Mat M, ll e) { // episode 21, on matrices
int k = M.size();
Mat R(k, vector<ll>(k, 0));
for (int i = 0; i < k; i++) R[i][i] = 1; // identity
for (; e > 0; e >>= 1, M = mul(M, M))
if (e & 1) R = mul(R, M);
return R;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
Mat T = {{1, 1, 1},
{1, 0, 0},
{0, 1, 0}};
cout << power(T, n)[0][0] << "\n"; // ways(n)
return 0;
}
| Input | Output |
|---|---|
10 |
274 |
0 |
1 (T⁰ = I) |
1000000000000000000 |
538436942 (instant) |
Entries are long long: each is below 10^9 + 7, and a product of two is below about 1.0 · 10^18, which fits (the limit is about 9.2 · 10^18); the % MOD comes right after every product.
A stress test
Episode 5's idea: compare with the plain loop on every small n.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Mat = vector<vector<ll>>;
const ll MOD = 1e9 + 7;
Mat mul(const Mat& A, const Mat& B) {
int k = A.size();
Mat C(k, vector<ll>(k, 0));
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
for (int t = 0; t < k; t++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
return C;
}
Mat power(Mat M, ll e) {
int k = M.size();
Mat R(k, vector<ll>(k, 0));
for (int i = 0; i < k; i++) R[i][i] = 1; // identity
for (; e > 0; e >>= 1, M = mul(M, M))
if (e & 1) R = mul(R, M);
return R;
}
ll loop(ll n) { // the O(n) DP
ll a = 1, b = 0, c = 0;
for (ll i = 1; i <= n; i++) { ll x = (a + b + c) % MOD; c = b; b = a; a = x; }
return a;
}
int main() {
Mat T = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
for (ll n = 0; n <= 2000; n++)
if (power(T, n)[0][0] != loop(n)) { cout << "mismatch at n = " << n; return 0; }
cout << "all 2001 tests passed";
}
Output: all 2001 tests passed.
Building T for any linear recurrence
For f(n) = c1·f(n−1) + c2·f(n−2) + … + ck·f(n−k):
- the top row is c1 c2 … ck;
- below it, 1s just under the diagonal shift the window (f(n−1) moves into the f(n−2) slot, and so on);
- a constant term + d: add a state that is always 1, put d in the top row's last column and a 1 in the last row's last column.
Example f(n) = 2f(n−1) + 3f(n−2) + 5 with state (f(n−1), f(n−2), 1):
| 2 3 5 |
| 1 0 0 |
| 0 0 1 |
Cost: O(k³ log n).
Part 2 · Problem F2 · Auto Routes
(Written for this course.) n stops (n ≤ 50), m one-way roads (several roads may join the same pair). Count the routes from stop 1 to stop n using exactly k rides (k ≤ 10^18), mod 10^9 + 7. Stops may repeat.
Let A[u][v] = number of roads from u to v (the adjacency matrix). Routes of k rides ending at v = Σ over u of (routes of k − 1 rides ending at u) · A[u][v]. Fixed multipliers again, so the answer is A^k[1][n] (indices from 0 in C++).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Mat = vector<vector<ll>>;
const ll MOD = 1e9 + 7;
Mat mul(const Mat& A, const Mat& B) {
int k = A.size();
Mat C(k, vector<ll>(k, 0));
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
for (int t = 0; t < k; t++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
return C;
}
Mat power(Mat M, ll e) {
int k = M.size();
Mat R(k, vector<ll>(k, 0));
for (int i = 0; i < k; i++) R[i][i] = 1; // identity
for (; e > 0; e >>= 1, M = mul(M, M))
if (e & 1) R = mul(R, M);
return R;
}
int main() {
int n, m;
ll k;
cin >> n >> m >> k;
Mat A(n, vector<ll>(n, 0)); // A[u][v] = roads u -> v
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
A[u - 1][v - 1]++;
}
cout << power(A, k)[0][n - 1] << "\n";
return 0;
}
Roads 1→2, 2→3, 3→1, 1→3:
| Input | Output | Routes |
|---|---|---|
3 4 2 + roads |
1 |
1→2→3 |
3 4 4 + roads |
2 |
1→3→1→2→3, 1→2→3→1→3 |
3 4 1000000000000000000 + roads |
13581 |
Cost: O(n³ log k) = 50³ · about 120 products ≈ 1.5 · 10^7.
Complexity vs the constraints
| Method | Time | n = 10^18 |
|---|---|---|
| plain loop | O(n) | about 31 years: TLE |
| matrix power, Problem F (k = 3) | O(27 · log n) | about 3,200 multiplications |
| matrix power, Problem F2 (k = 50) | O(k³ log n) | about 1.5 · 10^7 |
The matrix size k is the limit: k³ log n must stay around 10^8, so k up to roughly 100–200.
Common mistakes (and the real outputs)
Bug 1: int entries
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Mat = vector<vector<int>>; // saves memory?
const ll MOD = 1e9 + 7;
Mat mul(const Mat& A, const Mat& B) {
int k = A.size();
Mat C(k, vector<int>(k, 0));
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
for (int t = 0; t < k; t++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
return C;
}
Mat power(Mat M, ll e) { // episode 21, on matrices
int k = M.size();
Mat R(k, vector<int>(k, 0));
for (int i = 0; i < k; i++) R[i][i] = 1; // identity
for (; e > 0; e >>= 1, M = mul(M, M))
if (e & 1) R = mul(R, M);
return R;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;
cin >> n;
Mat T = {{1, 1, 1},
{1, 0, 0},
{0, 1, 0}};
cout << power(T, n)[0][0] << "\n"; // ways(n)
return 0;
}
10 → 274 (looks fine), 1000000000000000000 → -329855217. Each entry fits in an int, but A[i][t] * B[t][j] is int × int, about 10^18, and overflows before the % MOD. Fix: long long entries.
Bug 2: no identity
Deleting the line for (int i = 0; i < k; i++) R[i][i] = 1; leaves R as all zeros: 10 → 0 (expected 274). Zero times anything is zero.
Bug 3: int n
With int n; and input 1000000000000000000, the program prints 607581890 (expected 538436942): the value doesn't fit, so cin stores the largest int, 2147483647, and the program answers for that n.
Summary table
| Mistake | What you see | Why | Fix |
|---|---|---|---|
using Mat = vector<vector<int>>; |
-329855217 |
int × int overflows | long long entries |
Mat R(k, vector<ll>(k, 0)); without the diagonal |
0 instead of 274 |
R must start as I | R[i][i] = 1 |
int n; |
607581890 |
10^18 doesn't fit | long long n |
| the plain loop for 10^18 | Time Limit Exceeded | 10^18 steps | power(T, n) |
| wrong state(0) | off by one term | base values mixed up | check n = 0, 1, 2 by hand |
Mini project
Write a reusable struct Matrix with operator*, a static identity(k) and a power(e) method, then use it for: (1) Fibonacci(10^18); (2) the Rangoli Border; (3) f(n) = 2f(n−1) + 3f(n−2) + 5; (4) walks of length ≤ k (add a "counter" state). Stress test each against a plain loop for n ≤ 1000.
Practice
-
Fibonacci(10^18) mod 10^9 + 7 with F(0) = 0, F(1) = 1.
Answer
F(n) = [[1,1],[1,0]]^n[0][1]. F(10) = 55, F(10^18) mod 10^9 + 7 = <b>209783453</b>. -
f(n) = 2f(n−1) + 3f(n−2) + 5, f(0) = 0, f(1) = 1.
Answer
State (f(n−1), f(n−2), 1), matrix [[2,3,5],[1,0,0],[0,0,1]], f(n) = row 0 of T^(n−1) · (1, 0, 1). f(10) = <b>51667</b> (matches a loop); f(10^18) mod 10^9 + 7 = <b>965544602</b>. -
Domino tilings of a 2 × n strip with 1 × 2 dominoes.
Answer
The last column is either one vertical domino (n − 1 left) or two horizontal ones (n − 2 left): Fibonacci again, tilings(n) = F(n + 1). n = 10 → <b>89</b>; n = 10^18 → <b>680057396</b>. -
Routes of at most k rides in the Auto Routes sample.
Answer
Add a "total" state, or use the block matrix [[A, I],[0, I]]. For k = 4: 1 + 1 + 1 + 2 = <b>5</b> (A^1..A^4 give 1, 1, 1, 2 routes from stop 1 to stop 3). -
Without code: how many matrix products does power(T, 10) do?
Answer
10 = 1010₂: four squarings of M (one is wasted at the end) and two multiplications into R: about 6, versus 10 loop steps. For 10^18: about 60 + 30.
Quick quiz
f(n) = f(n−1) + 2·f(n−2). State (f(n−1), f(n−2)). Which T moves it one step?
A) {{1, 2}, {1, 0}} · B) {{1, 1}, {2, 0}} · C) {{2, 1}, {1, 0}} · D) {{1, 2}, {0, 1}}
Answer
A. The top row holds the multipliers 1 and 2; the second row copies f(n−1) into the f(n−2) slot: 1, 0.
Interview questions
- How do you compute the n-th Fibonacci number for n = 10^18? Matrix exponentiation: [[1,1],[1,0]]^n in O(log n) multiplications of 2 × 2 matrices.
- Why does square-and-multiply work for matrices? It only needs associativity of multiplication and an identity element; matrices have both.
- What is the complexity of matrix exponentiation? O(k³ log n) for k × k matrices.
- What does (A^k)[i][j] count for an adjacency matrix A? The number of walks of exactly k edges from i to j.
- How do you handle a constant term in a recurrence? Add a state that is always 1.
- Is matrix multiplication commutative? No, in general A·B ≠ B·A; powers of one matrix do commute with each other.
- What overflow do you watch for? Each product of two entries below the modulus can reach about 10^18: use 64-bit entries and reduce after every product.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Recurrence | A rule giving each term from earlier terms | f(n) = f(n−1) + f(n−2) |
| Base case | The starting values of a recurrence | ways(0) = 1 |
| Linear recurrence | Earlier terms times fixed numbers, added | 2f(n−1) + 3f(n−2) |
| Fibonacci numbers | 1, 1, 2, 3, 5, 8, … each the sum of the two before | ways to climb stairs by 1 or 2 |
| State vector | The values the next step needs | (a, b, c) = last three terms |
| Matrix | A grid of numbers; here one step of a linear recurrence | T = [[1,1,1],[1,0,0],[0,1,0]] |
| Matrix multiplication | Row times column, added up | [[1,1],[1,0]]² = [[2,1],[1,1]] |
| Identity matrix I | 1s on the diagonal; multiplying by it changes nothing | T⁰ = I |
| Associativity | (A·B)·C = A·(B·C) | lets us square |
| Matrix exponentiation | T^n by square-and-multiply in O(k³ log n) | 60 squarings for 10^18 |
| Square and multiply | Episode 21's fast power, using the bits of n | 10 = 1010₂ → T⁸ · T² |
| Adjacency matrix | A[u][v] = number of edges from u to v | auto roads |
| Walk | A route along edges that may repeat vertices | 1→3→1→2→3 |
| Stress test | Fast solution vs brute force on many small tests | all 2001 tests passed |
| Integer overflow | A value too big for its type wraps around | -329855217 |
Summary
- A linear recurrence builds each term from earlier ones with fixed multipliers; the O(n) loop is hopeless for n = 10^18.
- One step is a fixed matrix T times the state; n steps are T^n, computed by square and multiply from the identity: O(k³ log n).
- Rangoli Border: ways(n) = T^n[0][0] with T = [[1,1,1],[1,0,0],[0,1,0]]; 10^18 →
538436942. - The adjacency matrix power A^k counts walks of exactly k steps (
13581for k = 10^18 in the sample). - Real bugs: int entries (
-329855217), no identity (0),int n(607581890).
Solutions in C++, Java and Python
Problem F · Rangoli Border
C++: see "The accepted solution" above.
Java:
import java.util.*;
public class Main {
static final long MOD = 1_000_000_007L;
static long[][] mul(long[][] A, long[][] B) {
int k = A.length;
long[][] C = new long[k][k];
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
for (int t = 0; t < k; t++)
C[i][j] = (C[i][j] + A[i][t] * B[t][j]) % MOD;
return C;
}
static long[][] power(long[][] M, long e) {
int k = M.length;
long[][] R = new long[k][k];
for (int i = 0; i < k; i++) R[i][i] = 1; // identity
for (; e > 0; e >>= 1, M = mul(M, M))
if ((e & 1) == 1) R = mul(R, M);
return R;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long[][] T = {{1, 1, 1}, {1, 0, 0}, {0, 1, 0}};
System.out.println(power(T, n)[0][0]);
}
}
Python:
MOD = 10**9 + 7
def mul(A, B):
k = len(A)
return [[sum(A[i][t] * B[t][j] for t in range(k)) % MOD for j in range(k)] for i in range(k)]
def power(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)] # identity
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
n = int(input())
T = [[1, 1, 1], [1, 0, 0], [0, 1, 0]]
print(power(T, n)[0][0])
All three print 274 for 10 and 538436942 for 1000000000000000000.
Problem F2 · Auto Routes
Python (C++ above; Java is the same mul/power with an n × n matrix):
MOD = 10**9 + 7
def mul(A, B):
k = len(A)
return [[sum(A[i][t] * B[t][j] for t in range(k)) % MOD for j in range(k)] for i in range(k)]
def power(M, e):
k = len(M)
R = [[int(i == j) for j in range(k)] for i in range(k)]
while e > 0:
if e & 1:
R = mul(R, M)
M = mul(M, M)
e >>= 1
return R
n, m, k = map(int, input().split())
A = [[0] * n for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
A[u - 1][v - 1] += 1
print(power(A, k)[0][n - 1])