Matrix DP & Fast Linear Recurrences

Transitions written as matrix multiplication (Fibonacci, linear recurrences, graph walks of fixed length) use fast exponentiation on the transition matrix.

Why this shows up in the real world

Counting length-k walks between nodes. Linear recurrences mod prime.

Core idea (explained for students)

Build T where dp_{t+1} = T @ dp_t; answer uses T^k @ dp_0 with binary exponentiation.

Try this in Python

def mat_mul(A: list[list[int]], B: list[list[int]], mod: int) -> list[list[int]]:
    n = len(A)
    C = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            if A[i][k]:
                for j in range(n):
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C


def mat_pow(M: list[list[int]], e: int, mod: int) -> list[list[int]]:
    n = len(M)
    R = [[1 if i == j else 0 for j in range(n)] for i in range(n)]
    while e:
        if e & 1:
            R = mat_mul(R, M, mod)
        M = mat_mul(M, M, mod)
        e //= 2
    return R


fib = [[1, 1], [1, 0]]
print(mat_pow(fib, 10, 10**9 + 7)[0][1])

Common mistakes

• Dimension mismatch in matmul.
• Modulo every multiply to prevent blowup.

Key takeaways

• Precompute identity and test k=0, k=1 edge cases.