Nhân ma trận (Matrix Exponentiation)

Wiki › Thuật toán › Toán học

Nhân ma trận (Matrix Exponentiation)

huunguyen · Last updated 8, Tháng 4, 2026, 16:10

Nhân ma trận nhanh (Matrix Exponentiation) tính $M^{n}$ trong $O (K^{3} \log N)$ với $K \times K$ là kích thước ma trận — dùng để giải công thức truy hồi tuyến tính và đếm đường đi trong đồ thị trong $O (\log N)$ .

Nhân ma trận

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

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

Matrix mat_pow(Matrix A, long long n) {
    int sz = A.size();
    Matrix result(sz, vector<long long>(sz, 0));
    for (int i = 0; i < sz; i++) result[i][i] = 1;   // identity
    while (n > 0) {
        if (n & 1) result = multiply(result, A);
        A = multiply(A, A);
        n >>= 1;
    }
    return result;
}

Ứng dụng 1: Fibonacci

F_{n} = F_{n - 1} + F_{n - 2}

(\begin{matrix} F_{n + 1} \\ F_{n} \end{matrix}) = (^{\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) n} (\begin{matrix} 1 \\ 0 \end{matrix})

long long fibonacci(long long n) {
    if (n <= 1) return n;
    Matrix M = {{1, 1}, {1, 0}};
    Matrix R = mat_pow(M, n - 1);
    return R[0][0];   // F_n
}

Ứng dụng 2: Công thức truy hồi tuyến tính tổng quát

a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + \dots + c_{k} a_{n - k}

(\begin{matrix} a_{n} \\ a_{n - 1} \\ ⋮ \\ a_{n - k + 1} \end{matrix}) = (\begin{matrix} c_{1} & c_{2} & \dots & c_{k} \\ 1 & 0 & \dots & 0 \\ ⋮ & ⋱ & ⋮ \\ 0 & \dots & 1 & 0 \end{matrix}) (\begin{matrix} a_{n - 1} \\ a_{n - 2} \\ ⋮ \\ a_{n - k} \end{matrix})

// Tính a_n với công thức truy hồi bậc k
long long linear_recurrence(vector<long long> c, vector<long long> init, long long n) {
    int k = c.size();
    if (n < k) return init[n];

    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;

    Matrix R = mat_pow(M, n - k + 1);

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

Ứng dụng 3: Đếm đường đi độ dài $K$ trong đồ thị

$(A^{K}) [i] [j]$ = số đường đi độ dài đúng $K$ từ $i$ đến $j$ :

// Với ma trận kề A (N x N)
// Đường đi độ dài K từ s đến t:
Matrix A_k = mat_pow(adj_matrix, K);
long long paths = A_k[s][t];

Ứng dụng 4: DP trên đồ thị với bước cố định

Bài toán: đếm số cách đi $K$ bước trên đồ thị thỏa ràng buộc, dùng ma trận chuyển trạng thái.

Tối ưu: Cayley-Hamilton

Với công thức truy hồi bậc $K$ và $n$ rất lớn, có thể dùng Berlekamp-Massey tìm công thức rồi dùng Cayley-Hamilton để tính nhanh hơn $O (K^{2} \log N)$ .

Độ phức tạp

Bài toán	Độ phức tạp
$M^{n}$ ( $K \times K$ )	$O (K^{3} \log N)$
Fibonacci thứ $N$	$O (\log N)$
Truy hồi bậc $K$	$O (K^{3} \log N)$
Đường đi độ dài $K$ ( $N$ đỉnh)	$O (N^{3} \log K)$

Khi nào dùng Matrix Exponentiation?

Công thức truy hồi tuyến tính với $n \leq 10^{18}$ .
Đếm đường đi độ dài cố định trong đồ thị nhỏ.
DP với trạng thái ít ( $K \leq 100$ ) nhưng số bước nhiều.

Bình luận

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