Cấu trúc dữ liệu và Giải thuật Bài 68: Lũy thừa ma trận (Matrix Exponentiation) - Tính toán Fibonacci và Đồ thị với số mũ khổng lồ.

Bước sang Chương 15: Toán học hệ thống và Đại số cấu trúc, chúng ta đối mặt với một thách thức toán học thường xuất hiện trong các hệ thống tài chính phân tán hoặc mô hình hóa mạng lưới: Làm sao để tính toán các chuỗi hồi quy hoặc đường đi trên đồ thị với số mũ siêu lớn ($N = 10^{18}$)?

Ở Bài 55, chúng ta đã tối ưu hóa bài toán Fibonacci xuống độ phức tạp thời gian tuyến tính $O(N)$ bằng vòng lặp Bottom-Up. Tuy nhiên, nếu đề bài yêu cầu tìm số Fibonacci thứ $N = 10^{18}$, vòng lặp tuyến tính sẽ phải chạy đến ngàn năm sau mới xong. Để ép thời gian thực thi xuống mức $O(\log N)$ chớp nhoáng, kỹ sư hệ thống phải kết hợp giữa Lũy thừa nhị phân (Binary Exponentiation) và Lũy thừa ma trận (Matrix Exponentiation).

1. Bản chất toán học: Biến Lập trình động thành Phép nhân ma trận

Hãy bắt đầu từ công thức Fibonacci quen thuộc:

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

Thay vì tính toán đơn lẻ từng bước, ta có thể biểu diễn nó dưới dạng một hệ phương trình ma trận:

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}$$

Bằng cách quy nạp từ trường hợp cơ sở, ta thu được công thức tổng quát:

$$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}$$

Mọi bài toán hồi quy tuyến tính (Linear Recurrence) đều có thể quy đổi về việc tính lũy thừa của một ma trận vuông. Mà việc tính lũy thừa của một số hoặc một ma trận với số mũ $N$ khổng lồ hoàn toàn có thể được giải quyết bằng thuật toán Lũy thừa nhị phân (Binary Exponentiation / Square-and-Multiply) trong thời gian $O(\log N)$.

2. Triển khai Lũy thừa ma trận bằng Golang

Dưới đây là mã nguồn chuẩn mực thực hiện phép nhân ma trận và Lũy thừa ma trận để tính toán số Fibonacci cực lớn với cơ chế chia lấy dư (MOD) chống tràn số:

Go

package main

import "fmt"

const MOD = 1000000007

// Định nghĩa kiểu dữ liệu Ma trận vuông (N x N)
type Matrix [][]int64

// Hàm nhân hai ma trận A và B kích thước N x N
func multiply(A, B Matrix) Matrix {
	n := len(A)
	C := make(Matrix, n)
	for i := range C {
		C[i] = make([]int64, n)
		for j := range C[i] {
			var sum int64 = 0
			for k := 0; k < n; k++ {
				sum = (sum + A[i][k]*B[k][j]) % MOD
			}
			C[i][j] = sum
		}
	}
	return C
}

// Hàm tính lũy thừa ma trận A^p với độ phức tạp O(M^3 * log p)
func power(A Matrix, p int64) Matrix {
	n := len(A)
	// Khởi tạo Ma trận đơn vị (Identity Matrix)
	res := make(Matrix, n)
	for i := range res {
		res[i] = make([]int64, n)
		res[i][i] = 1
	}

	base := A
	for p > 0 {
		if p%2 == 1 {
			res = multiply(res, base)
		}
		base = multiply(base, base)
		p /= 2
	}
	return res
}

// Tính số Fibonacci thứ N với N cực lớn (ví dụ: 10^18) trong thời gian O(log N)
func FibMatrix(n int64) int64 {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}

	// Ma trận cơ sở T = [[1, 1], [1, 0]]
	T := Matrix{
		{1, 1},
		{1, 0},
	}

	// Tính T^(n-1)
	Tn := power(T, n-1)

	// F(n) nằm ở vị trí [0][0] sau khi nhân với vector khởi tạo [F(1), F(0)]^T
	// Vì F(1) = 1 và F(0) = 0, kết quả chính là thành phần Tn[0][0] * 1 + Tn[0][1] * 0
	return Tn[0][0]
}

func main() {
	var n int64 = 1000000000000 // 1 nghìn tỷ!
	fmt.Printf("Đang tính số Fibonacci thứ %d...\n", n)
	
	result := FibMatrix(n)
	fmt.Printf("Kết quả (mod 10^9 + 7): %d\n", result)
}

3. Phân tích Hiệu năng (Big-O)

• Thời gian (Time Complexity): $O(M^3 \cdot \log N)$ (với $M$ là kích thước của ma trận, trong trường hợp Fibonacci là $M = 2$, nên độ phức tạp thực tế là $O(\log N)$). Thuật toán cho phép tính toán các số mũ lên tới $10^{18}$ chỉ trong vài chục bước lặp.

• Không gian (Space Complexity): $O(M^2)$ để lưu trữ các ma trận tạm trong quá trình nhân, cực kỳ tiết kiệm bộ nhớ.

4. Ứng dụng Thực tế trong Hệ thống Enterprise

Lũy thừa ma trận không chỉ giới hạn ở việc tính toán dãy số Fibonacci, nó là công cụ toán học tối thượng trong nhiều bài toán kỹ thuật cấp cao:

• Đếm số đường đi có độ dài chính xác $K$ trên Đồ thị (Graph Path Counting): Nếu bạn muốn biết có bao nhiêu cách di chuyển từ đỉnh $u$ đến đỉnh $v$ trên một đồ thị thông qua đúng $K$ bước cạnh, bạn chỉ cần lấy Ma trận kề (Adjacency Matrix) của đồ thị đem nâng lên lũy thừa $K$ ($A^K$). Phần tử tại hàng $u$ cột $v$ của ma trận kết quả chính là số lượng đường đi cần tìm.

• Mô phỏng Tài chính dài hạn & Lãi suất kép (Compound Interest Systems): Các hệ thống dự báo tài chính quy mô lớn tính toán trạng thái dòng tiền qua hàng triệu bước thời gian rời rạc bằng cách sử dụng các hệ phương trình ma trận chuyển đổi trạng thái.

Việc làm chủ Lũy thừa ma trận hoàn thiện mảnh ghép cuối cùng trong tư duy thuật toán tối ưu hóa cấp độ cao.