SyntaxPilot
Courses/Competitive Programming/Lesson 29

Competitive Programming · Lesson 29 of 90 · 13 min

Matrix exponentiation for linear recurrences

queued

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

  1. 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>.

  2. 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>.

  3. 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>.

  4. 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).

  5. 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

  1. 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.
  2. Why does square-and-multiply work for matrices? It only needs associativity of multiplication and an identity element; matrices have both.
  3. What is the complexity of matrix exponentiation? O(k³ log n) for k × k matrices.
  4. What does (A^k)[i][j] count for an adjacency matrix A? The number of walks of exactly k edges from i to j.
  5. How do you handle a constant term in a recurrence? Add a state that is always 1.
  6. Is matrix multiplication commutative? No, in general A·B ≠ B·A; powers of one matrix do commute with each other.
  7. 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 (13581 for 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])