DP nhân ma trận (Matrix Exponentiation)

Wiki › Thuật toán › Quy hoạch động (DP)

DP nhân ma trận (Matrix Exponentiation)

huunguyen · Last updated 3, Tháng 4, 2026, 20:31

DP nhân ma trận là kỹ thuật kết hợp quy hoạch động với lũy thừa ma trận nhanh để tính các công thức truy hồi tuyến tính khi $N$ rất lớn (lên tới $10^{18}$ ).

Ý tưởng cốt lõi

Nếu công thức truy hồi có dạng tuyến tính:

(\begin{matrix} f (n) \\ f (n - 1) \\ ⋮ \end{matrix}) = M \cdot (\begin{matrix} f (n - 1) \\ f (n - 2) \\ ⋮ \end{matrix})

Thì:

(\begin{matrix} f (n) \\ ⋮ \end{matrix}) = M^{n - 1} \cdot (\begin{matrix} f (1) \\ ⋮ \end{matrix})

Tính $M^{n - 1}$ bằng fast exponentiation trong $O (k^{3} \log N)$ với $k$ là kích thước ma trận.

Nhân ma trận và lũy thừa nhanh

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

const long long MOD = 1e9 + 7;
typedef vector<vector<long long>> Matrix;

int sz; // kích thước ma trận

Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C(sz, vector<long long>(sz, 0));
    for (int i = 0; i < sz; i++)
        for (int k = 0; k < sz; k++) {
            if (A[i][k] == 0) continue;
            for (int j = 0; j < sz; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        }
    return C;
}

Matrix matpow(Matrix A, long long p) {
    Matrix result(sz, vector<long long>(sz, 0));
    for (int i = 0; i < sz; i++) result[i][i] = 1; // ma trận đơn vị
    while (p > 0) {
        if (p & 1) result = multiply(result, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return result;
}

Ví dụ 1: Fibonacci thứ $N$ ( $N \leq 10^{18}$ )

Công thức: $F (n) = F (n - 1) + F (n - 2)$ , với $F (1) = F (2) = 1$ .

Ma trận chuyển:

(\begin{matrix} F (n + 1) \\ F (n) \end{matrix}) = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) \cdot (\begin{matrix} F (n) \\ F (n - 1) \end{matrix})

long long fibonacci(long long n) {
    if (n <= 2) return 1;
    sz = 2;
    Matrix M = {{1, 1}, {1, 0}};
    Matrix R = matpow(M, n - 1);
    // R * [F(2), F(1)]^T = R * [1, 1]^T
    return (R[0][0] + R[0][1]) % MOD;
}

Ví dụ 2: Truy hồi bậc $k$

Công thức: $f (n) = c_{1} f (n - 1) + c_{2} f (n - 2) + \dots + c_{k} f (n - k)$

Ma trận chuyển $k \times k$ :

M = (\begin{matrix} c_{1} & c_{2} & c_{3} & \dots & c_{k} \\ 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 1 & 0 \end{matrix})

// Ví dụ: f(n) = 2f(n-1) + 3f(n-2) + f(n-3)
// c = {2, 3, 1}, k = 3
long long solve(long long n, vector<long long> c, vector<long long> init) {
    int k = c.size();
    sz = k;
    Matrix M(k, vector<long long>(k, 0));
    for (int j = 0; j < k; j++) M[0][j] = c[j];
    for (int i = 1; i < k; i++) M[i][i-1] = 1;

    if (n <= k) return init[n - 1];
    Matrix R = matpow(M, n - k);
    long long ans = 0;
    for (int j = 0; j < k; j++)
        ans = (ans + R[0][j] % MOD * init[k - 1 - j]) % MOD;
    return ans;
}

Ví dụ 3: Đếm đường đi dài đúng $N$ bước trên đồ thị

Bài toán: Cho đồ thị $k$ nút. Đếm số đường đi dài đúng $N$ bước từ $s$ đến $t$ (modulo $10^{9} + 7$ ).

Nhận xét: Nếu $A$ là ma trận kề của đồ thị, thì $A^{N} [s] [t]$ = số đường đi dài $N$ từ $s$ đến $t$ .

long long countPaths(int k, vector<vector<int>>& edges, long long N, int s, int t) {
    sz = k;
    Matrix A(k, vector<long long>(k, 0));
    for (auto& e : edges) A[e[0]][e[1]]++;

    Matrix R = matpow(A, N);
    return R[s][t];
}

Ví dụ 4: DP tuyến tính với hằng số cộng thêm

Bài toán: $f (n) = f (n - 1) + f (n - 2) + n$ , với $f (0) = f (1) = 1$ .

Thêm biến phụ để tuyến tính hóa: vector trạng thái $[f (n), f (n - 1), n, 1]^{T}$ .

(\begin{matrix} f (n + 1) \\ f (n) \\ n + 1 \\ 1 \end{matrix}) = (\begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix}) \cdot (\begin{matrix} f (n) \\ f (n - 1) \\ n \\ 1 \end{matrix})

Mẹo chung: Để xử lý số hạng $n$ , $n^{2}$ , hằng số trong truy hồi, thêm chúng vào vector trạng thái.

Ví dụ 5: DP trên lưới với bước nhảy lớn

Bài toán: Đi trên lưới $k$ ô, mỗi bước đi sang ô bên cạnh hoặc đứng yên. Sau đúng $N$ bước, có bao nhiêu cách đứng tại ô $t$ ?

// Mỗi ô là một trạng thái, ma trận chuyển A[i][j] = 1 nếu có thể đi từ j đến i
// Tính A^N, lấy cột s

Độ phức tạp


Thời gian	$O (k^{3} \log N)$
Không gian	$O (k^{2})$

Với $k \leq 100$ và $N \leq 10^{18}$ : $100^{3} \times 60 \approx 6 \times 10^{7}$ — vừa đủ.

Nhận dạng nhanh

Dấu hiệu	Kỹ thuật
Truy hồi tuyến tính, $N \leq 10^{18}$	Matrix exponentiation
Đếm đường đi đúng $N$ bước trên đồ thị nhỏ	$A^{N}$
DP có trạng thái cố định, transition tuyến tính, $N$ lớn	Biểu diễn thành ma trận

Lưu ý khi cài đặt

Luôn lấy modulo sau mỗi phép nhân để tránh overflow.
Dùng long long vì $A [i] [k] \times B [k] [j]$ có thể tới $10^{18}$ .
Ma trận đơn vị (identity matrix) là phần tử trung tính khi nhân — dùng làm giá trị khởi tạo trong matpow.

Bình luận

Không có bình luận tại thời điểm này.