Transfer Matrix Method — Counting Paths via Matrix Exponentiation

January 2026 · 25 min read

The Transfer Matrix Idea

Many combinatorial problems reduce to counting walks of length n in a finite directed graph. The transfer matrix method exploits a beautifully simple fact from linear algebra: if A is the adjacency matrix of a graph with k vertices, then Aⁿ[i][j] equals the number of walks of exactly n steps from vertex i to vertex j.

Why does this work? Consider the base case: A¹[i][j] is 1 exactly when there is an edge from i to j — i.e., a walk of length 1. For the inductive step, a walk of length n from i to j must pass through some intermediate vertex m at step n−1. The number of such walks is Aⁿ⁻¹[i][m] · A[m][j], and summing over all m gives the matrix product (Aⁿ⁻¹ · A)[i][j] = Aⁿ[i][j].

Connection to Linear Recurrences

The transfer matrix method is deeply connected to linear recurrences. If a counting sequence satisfies a_n = c₁a_n−1 + c₂a_n−2 + … + c_ka_n−k, we can encode the recurrence as a k×k companion matrix and compute a_n via matrix exponentiation in O(k³ log n). This turns a problem that might require O(n) DP into O(k³ log n), which is crucial when n can be 10¹⁸.

The "transfer matrix" is the matrix T whose entry T[s][t] equals the number of ways to transition from state s to state t in one step. After n steps the answer is read from Tⁿ. In the simplest case T is just the adjacency matrix, but in more complex scenarios the states represent DP profiles, automaton nodes, or other abstractions.

Matrix Exponentiation Refresher

Fast matrix exponentiation is the engine that powers the transfer matrix method. We compute Mⁿ via repeated squaring in O(k³ log n), where k is the matrix dimension. All arithmetic is typically done modulo a prime (10⁹+7).

Algorithm

C++ Template

const int MOD = 1e9 + 7;

struct Matrix {
    int n;
    vector<vector<long long>> a;
    Matrix(int _n) : n(_n), a(_n, vector<long long>(_n, 0)) {}
    Matrix operator*(const Matrix& o) const {
        Matrix res(n);
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++) if (a[i][k])
                for (int j = 0; j < n; j++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
        return res;
    }
};

Matrix mat_pow(Matrix m, long long p) {
    int n = m.n;
    Matrix res(n);
    for (int i = 0; i < n; i++) res.a[i][i] = 1; // identity
    while (p > 0) {
        if (p & 1) res = res * m;
        m = m * m;
        p >>= 1;
    }
    return res;
}

The if (a[i][k]) guard in the multiplication skips zero entries, which can significantly speed up sparse transfer matrices — a common scenario in profile DP where most transitions are invalid.

Profile Dynamic Programming

Profile DP (also called "broken profile" DP) is the most common application of the transfer matrix method in competitive programming. The canonical problem: count the number of ways to tile an m×n grid with 1×2 dominoes.

Setting Up States

We process the grid column by column (left to right). After placing dominoes in the first j columns, some cells in column j+1 are already occupied by horizontal dominoes that started in column j. The profile (or "state") of column j is a bitmask of m bits, where bit i = 1 means row i of the next column is already filled.

There are 2^m possible profiles. The transfer matrix T is a 2^m × 2^m matrix where T[mask1][mask2] = 1 if there exists a valid way to fill column j such that the incoming profile is mask1 and the outgoing profile (into column j+1) is mask2.

Building the Transfer Matrix

To compute T, we iterate over all pairs (mask1, mask2) and check validity. For each column, we process rows top to bottom. At each row i:

• If bit i of mask1 is 1, that cell is already occupied → bit i of mask2 must be 0 (no domino extends further right).
• If bit i of mask1 is 0, we must place a domino covering this cell. Two options:
  • Horizontal domino: extends into the next column → set bit i of mask2 to 1.
  • Vertical domino: covers row i and row i+1 in the current column → bit i+1 of mask1 must also be 0, and we advance i by 2.

Worked Example: 3×n Tiling

For m = 3, there are 2³ = 8 possible profiles. The transfer matrix T is 8×8. We build it by the rules above. The answer for a 3×n grid is (Tⁿ)[0][0] — we start with an empty profile (mask = 0) and need to end with an empty profile (all cells of the last column fully covered).

For 3×n, a well-known closed form exists: the count is 0 when n is odd, and follows a linear recurrence a_n = 4·a_n−2 − a_n−4 for even n (with a₀ = 1, a₂ = 3). The matrix approach confirms this and generalizes effortlessly to any m.

// Build transfer matrix for m x n domino tiling
// m = number of rows (small), n = number of columns (large)
void build_transfer(int m, Matrix& T) {
    int S = 1 << m;
    // Try all ways to fill a column given incoming mask
    function<void(int, int, int)> fill = [&](int row, int in_mask, int out_mask) {
        if (row == m) {
            T.a[in_mask][out_mask] = 1;
            return;
        }
        if ((in_mask >> row) & 1) {
            // row already filled by horizontal domino from prev column
            fill(row + 1, in_mask, out_mask);
        } else {
            // Option 1: place horizontal domino extending into next column
            fill(row + 1, in_mask, out_mask | (1 << row));
            // Option 2: place vertical domino (need row+1 also free)
            if (row + 1 < m && !((in_mask >> (row + 1)) & 1)) {
                fill(row + 2, in_mask, out_mask);
            }
        }
    };
    for (int mask = 0; mask < S; mask++)
        fill(0, mask, 0);
}

long long count_tilings(int m, long long n) {
    int S = 1 << m;
    Matrix T(S);
    build_transfer(m, T);
    Matrix res = mat_pow(T, n);
    return res.a[0][0];
}

Counting Strings with Forbidden Patterns

A powerful application of the transfer matrix method: count the number of strings of length n over an alphabet Σ that avoid a set of forbidden substrings P = {p₁, p₂, …, p_t}. The idea is to combine an Aho-Corasick automaton with matrix exponentiation.

Step 1: Build the Aho-Corasick Automaton

Insert all forbidden patterns into a trie and compute failure links (just like the standard Aho-Corasick construction). Mark any node that corresponds to the end of a forbidden pattern — or any node whose suffix link chain reaches such a node — as a forbidden state.

Step 2: Construct the Transfer Matrix

Let the automaton have k non-forbidden states (including the root). Build a k×k transfer matrix T where T[u][v] = number of characters c ∈ Σ such that the automaton transitions from state u to state v on character c, and v is not a forbidden state.

Step 3: Exponentiate

The answer is the sum of all entries in row 0 (the root) of Tⁿ:

answer = Σ_j Tⁿ[0][j]

Each entry Tⁿ[0][j] counts the number of valid strings of length n that leave the automaton in non-forbidden state j.

// Aho-Corasick + matrix exponentiation for forbidden substrings
// Alphabet size = alpha (e.g., 26 for lowercase letters)
struct AhoCorasick {
    vector<array<int, 26>> go;
    vector<int> fail, is_end;
    int new_node() {
        go.push_back({});
        go.back().fill(-1);
        fail.push_back(0);
        is_end.push_back(0);
        return (int)go.size() - 1;
    }
    AhoCorasick() { new_node(); } // root = 0

    void add(const string& s) {
        int cur = 0;
        for (char c : s) {
            int ch = c - 'a';
            if (go[cur][ch] == -1) go[cur][ch] = new_node();
            cur = go[cur][ch];
        }
        is_end[cur] = 1;
    }

    void build() {
        queue<int> q;
        for (int c = 0; c < 26; c++) {
            if (go[0][c] == -1) go[0][c] = 0;
            else { fail[go[0][c]] = 0; q.push(go[0][c]); }
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            is_end[u] |= is_end[fail[u]]; // propagate forbidden
            for (int c = 0; c < 26; c++) {
                if (go[u][c] == -1)
                    go[u][c] = go[fail[u]][c];
                else {
                    fail[go[u][c]] = go[fail[u]][c];
                    q.push(go[u][c]);
                }
            }
        }
    }

    Matrix transfer_matrix() {
        int sz = (int)go.size();
        // Collect non-forbidden states
        vector<int> id(sz, -1);
        int cnt = 0;
        for (int i = 0; i < sz; i++)
            if (!is_end[i]) id[i] = cnt++;
        Matrix T(cnt);
        for (int u = 0; u < sz; u++) if (!is_end[u]) {
            for (int c = 0; c < 26; c++) {
                int v = go[u][c];
                if (!is_end[v])
                    T.a[id[u]][id[v]]++;
            }
        }
        return T;
    }
};

long long count_valid_strings(vector<string>& forbidden, long long n) {
    AhoCorasick ac;
    for (auto& s : forbidden) ac.add(s);
    ac.build();
    Matrix T = ac.transfer_matrix();
    Matrix res = mat_pow(T, n);
    long long ans = 0;
    for (int j = 0; j < res.n; j++)
        ans = (ans + res.a[0][j]) % MOD;
    return ans;
}

Linear Recurrences via Transfer Matrix

The most foundational application: given a linear recurrence a_n = c₁·a_n−1 + c₂·a_n−2 + … + c_k·a_n−k with known initial values a₀, …, a_k−1, compute a_n for astronomically large n.

The Companion Matrix

Define the state vector v_n = (a_n, a_n−1, …, a_n−k+1)^T. The recurrence becomes v_n = C · v_n−1, where C is the companion matrix:

Therefore v_n = Cⁿ · v₀, and a_n is the first component of this product.

Fibonacci Example

The Fibonacci recurrence F_n = F_n−1 + F_n−2 has the companion matrix:

Then (F_n+1, F_n)^T = Cⁿ · (F₁, F₀)^T. Computing Cⁿ takes O(2³ log n) = O(8 log n) — about 240 multiplications for n = 10¹⁸.

General k-th Order Recurrence

// Solve: a[n] = c[0]*a[n-1] + c[1]*a[n-2] + ... + c[k-1]*a[n-k]
// init[] = { a[0], a[1], ..., a[k-1] }
long long solve_recurrence(vector<long long> c, vector<long long> init, long long n) {
    int k = (int)c.size();
    if (n < k) return init[n] % MOD;

    // Build companion matrix
    Matrix C(k);
    for (int j = 0; j < k; j++) C.a[0][j] = c[j] % MOD;
    for (int i = 1; i < k; i++) C.a[i][i - 1] = 1;

    Matrix Cn = mat_pow(C, n);
    long long ans = 0;
    for (int j = 0; j < k; j++)
        ans = (ans + Cn.a[0][j] % MOD * (init[j] % MOD)) % MOD;
    return (ans + MOD) % MOD;
}

Kitamasa / Bostan-Mori Sketch

Instead of exponentiating the full k×k matrix, we compute xⁿ mod p(x) where p(x) is the characteristic polynomial. This polynomial modular exponentiation uses O(k log k) per multiplication step (via NTT) and O(log n) steps, giving O(k log k · log n) total — much faster than O(k³ log n) for large k.

Concretely, Bostan-Mori computes the n-th term of a rational generating function P(x)/Q(x) in O(k log k · log n) by repeatedly halving n:

• Replace Q(x) with Q(x)·Q(−x), then keep only even-power terms.
• Replace P(x) with appropriate even/odd parts depending on whether n is even or odd.
• Halve n and repeat.

After O(log n) iterations, n reaches 0 and the answer is P(0)/Q(0).

C++ Implementation

Below are complete, contest-ready implementations that tie together the ideas above.

Complete Matrix Struct with Multiply and Power

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

struct Matrix {
    int n;
    vector<vector<long long>> a;
    Matrix() : n(0) {}
    Matrix(int _n) : n(_n), a(_n, vector<long long>(_n, 0)) {}

    static Matrix identity(int n) {
        Matrix I(n);
        for (int i = 0; i < n; i++) I.a[i][i] = 1;
        return I;
    }

    Matrix operator*(const Matrix& o) const {
        assert(n == o.n);
        Matrix res(n);
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++) {
                if (!a[i][k]) continue; // skip zeros
                for (int j = 0; j < n; j++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * o.a[k][j]) % MOD;
            }
        return res;
    }

    Matrix power(long long p) const {
        Matrix res = identity(n);
        Matrix base = *this;
        while (p > 0) {
            if (p & 1) res = res * base;
            base = base * base;
            p >>= 1;
        }
        return res;
    }
};

Profile DP: Domino Tiling (Full Solution)

// Count ways to tile an m x n grid with 1x2 dominoes
// m <= 6 (small), n up to 1e18
int main() {
    int m;
    long long n;
    cin >> m >> n;

    int S = 1 << m;
    Matrix T(S);

    // Build transfer matrix via recursive column filling
    function<void(int, int, int)> fill = [&](int row, int in_mask, int out_mask) {
        if (row == m) {
            T.a[in_mask][out_mask] = 1;
            return;
        }
        if ((in_mask >> row) & 1) {
            // cell already filled by horizontal domino from previous column
            fill(row + 1, in_mask, out_mask);
        } else {
            // horizontal domino: occupies this cell and extends into next column
            fill(row + 1, in_mask, out_mask | (1 << row));
            // vertical domino: occupies this cell and the one below
            if (row + 1 < m && !((in_mask >> (row + 1)) & 1))
                fill(row + 2, in_mask, out_mask);
        }
    };

    for (int mask = 0; mask < S; mask++)
        fill(0, mask, 0);

    Matrix res = T.power(n);
    cout << res.a[0][0] << "\n";
    return 0;
}

Aho-Corasick + Matrix Exp: String Counting (Full Solution)

// Count strings of length n over {a..z} avoiding all forbidden substrings
int main() {
    int t;
    long long n;
    cin >> t >> n;

    AhoCorasick ac; // as defined in the section above
    for (int i = 0; i < t; i++) {
        string s; cin >> s;
        ac.add(s);
    }
    ac.build();

    Matrix T = ac.transfer_matrix();
    Matrix res = T.power(n);

    long long ans = 0;
    for (int j = 0; j < res.n; j++)
        ans = (ans + res.a[0][j]) % MOD;
    cout << ans << "\n";
    return 0;
}

Count Paths of Exact Length k in a Graph

// Given a directed graph with V vertices and edges,
// count the number of walks of exactly length k from src to dst.
int main() {
    int V, E;
    long long k;
    int src, dst;
    cin >> V >> E >> k >> src >> dst;

    Matrix A(V);
    for (int i = 0; i < E; i++) {
        int u, v;
        cin >> u >> v;
        A.a[u][v]++; // handles multi-edges
    }

    Matrix res = A.power(k);
    cout << res.a[src][dst] << "\n";
    return 0;
}

CP Applications

The transfer matrix method appears across a wide range of competitive programming problems. Here are the major categories and representative examples.

1. Grid Tiling

Tile an m×n grid with various tile shapes. The transfer matrix dimension is 2^m (or more for complex tiles). Classic examples:

• CSES — Counting Tilings — Tile a 2×n grid with 1×2 dominoes. Answer follows the Fibonacci sequence!
• CF 8C — Looking for Order — Bitmask DP on objects; transfer matrix speeds up the transition.

2. Counting Paths of Fixed Length

Given a graph, count walks of exactly k steps between two vertices. This is the most direct application of A^k.

• CSES — Graph Paths I — Count paths of length k in a graph. Direct matrix exponentiation.
• CSES — Graph Paths II — Find shortest path of exactly k edges using min-plus matrix semiring.

3. String Counting with Constraints

Count strings avoiding forbidden substrings (Aho-Corasick + matrix exp) or matching a regular language (DFA + matrix exp):

• CF 1096G — Lucky Tickets — Combine NTT with matrix-like reasoning on digit constraints.
• CF 506E — Mr. Kitayuta's Gift — Automaton states + matrix exponentiation for palindrome counting.

4. Linear Recurrences

Any problem where the answer satisfies a linear recurrence with constant coefficients and n is large:

• CSES — Fibonacci Numbers — Classic 2×2 matrix exponentiation for F_n mod 10⁹+7.
• CF 166E — Tetrahedron — Count paths of length n on a tetrahedron graph. 4×4 matrix (reduces to 2×2 by symmetry).

5. Advanced: Semiring Generalizations

Matrix exponentiation works over any semiring, not just (+, ×) over integers mod p. Common semirings in CP:

• (min, +) — shortest path of exactly k edges (tropical semiring).
• (max, +) — longest path of exactly k edges.
• (OR, AND) — reachability in k steps (boolean semiring).
• (+, ×) over matrices — standard counting.

Summary

The transfer matrix method is one of the most versatile tools in the competitive programmer's arsenal. Here is the recipe at a glance:

1. Identify the states. These might be bitmask profiles, automaton nodes, or abstract DP states. The number of states k determines feasibility.
2. Build the transfer matrix T. T[s][t] = number of ways to go from state s to state t in one step.
3. Exponentiate. Compute Tⁿ in O(k³ log n). Read the answer from the appropriate entry.