Nhân Ma Trận Nhanh: Tính Số Fibonacci Thứ 10^18 Trong O(log N)
Dãy số Fibonacci là một trong những khái niệm quen thuộc nhất với mọi lập trình viên. Công thức truy hồi \(F(n) = F(n-1) + F(n-2)\) với hai giá trị khởi tạo \(F(0) = 0\) và \(F(1) = 1\) có thể được tính dễ dàng bằng vòng lặp trong thời gian \(O(N)\). Tuy nhiên, trong các kỳ thi học sinh giỏi và lập trình thi đấu, đề bài thường đưa ra giới hạn \(N\) khổng lồ, ví dụ \(N = 10^{18}\). Với giới hạn này, một vòng lặp đơn giản sẽ mất hàng triệu năm để hoàn thành.
Làm thế nào chúng ta có thể vượt qua rào cản thời gian tuyến tính để tìm ra \(F(10^{18}) \pmod{10^9+7}\) chỉ trong chưa đầy 0.001 giây? Câu trả lời nằm ở sự kết hợp giữa Đại số tuyến tính (Nhân ma trận) và Thuật toán lũy thừa nhị phân (Binary Exponentiation). Kỹ thuật này không chỉ áp dụng cho dãy Fibonacci mà còn là chìa khóa vạn năng để giải quyết mọi hệ thức truy hồi tuyến tính và các bài toán quy hoạch động đếm đường đi trên đồ thị.
1. Biểu diễn hệ thức truy hồi dưới dạng ma trận chuyển trạng thái
Xét hệ thức truy hồi bậc hai của dãy Fibonacci: \[F(n) = 1 \cdot F(n-1) + 1 \cdot F(n-2)\] \[F(n-1) = 1 \cdot F(n-1) + 0 \cdot F(n-2)\]
Chúng ta có thể gom hai phương trình trên thành một phương trình nhân ma trận duy nhất:
\[\begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n-1) \\ F(n-2) \end{pmatrix}\]
Đặt ma trận vuông cấp 2: \[T = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\]
Đây được gọi là ma trận chuyển trạng thái (Transition Matrix). Lần ngược liên tiếp \(n - 1\) lần về vector trạng thái ban đầu, ta thu được công thức đóng:
\[\begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix} = T^{n-1} \begin{pmatrix} F(1) \\ F(0) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix}\]
Như vậy, bài toán tính số Fibonacci thứ \(N\) được quy về bài toán tính lũy thừa ma trận \(T^{N - 1}\).
2. Phép nhân ma trận và Lũy thừa nhị phân
Phép nhân hai ma trận vuông
Cho hai ma trận vuông cấp \(K\): \(A\) và \(B\). Ma trận tích \(C = A \times B\) được xác định theo công thức: \[C_{i, j} = \sum_{k=0}^{K-1} A_{i, k} \times B_{k, j} \pmod{10^9+7}\] Phép nhân hai ma trận cấp \(K\) đòi hỏi 3 vòng lặp lồng nhau với độ phức tạp thời gian là \(O(K^3)\). Với dãy Fibonacci, \(K = 2\), phép nhân chỉ tốn đúng \(2^3 = 8\) phép tính!
Thuật toán lũy thừa nhị phân ma trận
Tương tự như tính lũy thừa của số thực \(a^M\), phép nhân ma trận có tính chất kết hợp \((A \times B) \times C = A \times (B \times C)\), do đó ta hoàn toàn áp dụng được tư duy chia để trị:
- Nếu số mũ \(M\) chẵn: \(T^M = (T^{M / 2})^2\).
- Nếu số mũ \(M\) lẻ: \(T^M = T \times T^{M - 1}\).
Vòng lặp chỉ chạy \(\lfloor \log_2 M \rfloor + 1\) lần; mỗi lần có một phép bình phương, cộng thêm một phép nhân vào kết quả khi bit đang xét bằng 1, nên tổng số phép nhân ma trận không quá \(2(\lfloor \log_2 M \rfloor + 1)\). Với \(N = 10^{18}\), số mũ \(M = 10^{18} - 1 < 2^{60}\) có 60 bit, trong đó 41 bit bằng 1: đoạn code bên dưới thực hiện 60 phép bình phương và 41 phép nhân vào kết quả, tổng cộng chỉ 101 phép nhân ma trận \(2 \times 2\)! Tổng độ phức tạp thời gian là \(O(K^3 \log N)\), một tốc độ vượt trội tuyệt đối so với thuật toán tuyến tính.
3. Cài đặt C++17 và Python 3 chuẩn thi đấu
Dưới đây là mã nguồn hoàn chỉnh có cấu trúc rõ ràng, hỗ trợ lấy modulo \(10^9 + 7\) chuẩn xác:
Cài đặt C++17
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
typedef vector<vector<long long>> Matrix;
// Nhan hai ma tran vuong 2x2 co lay modulo
Matrix multiply(const Matrix& A, const Matrix& B) {
Matrix C(2, vector<long long>(2, 0));
for (int i = 0; i < 2; ++i) {
for (int k = 0; k < 2; ++k) {
for (int j = 0; j < 2; ++j) {
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
}
}
}
return C;
}
// Luy thua nhi phan ma tran T^exp trong O(K^3 * log exp)
Matrix power(Matrix A, long long exp) {
// Khoi tao ma tran don vi I (Identity Matrix)
Matrix res = {{1, 0}, {0, 1}};
while (exp > 0) {
if (exp % 2 == 1) res = multiply(res, A);
A = multiply(A, A);
exp /= 2;
}
return res;
}
// Tinh so Fibonacci thu n trong O(log n)
long long fibonacci(long long n) {
if (n == 0) return 0;
if (n == 1) return 1;
Matrix T = {{1, 1}, {1, 0}};
Matrix Tn = power(T, n - 1);
// Vector trang thai ban dau: [F(1), F(0)]^T = [1, 0]^T
// F(n) = Tn[0][0] * 1 + Tn[0][1] * 0 = Tn[0][0]
return Tn[0][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// F(10) = 55
cout << fibonacci(10) << '\n';
// F(10^9) mod 10^9+7
cout << fibonacci(1000000000LL) << '\n';
return 0;
}
Cài đặt Python 3
import sys
MOD = 10**9 + 7
def multiply(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
C = [[0, 0], [0, 0]]
for i in range(2):
for k in range(2):
for j in range(2):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
return C
def power(A: list[list[int]], exp: int) -> list[list[int]]:
res = [[1, 0], [0, 1]]
while exp > 0:
if exp % 2 == 1:
res = multiply(res, A)
A = multiply(A, A)
exp //= 2
return res
def fibonacci(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
T = [[1, 1], [1, 0]]
Tn = power(T, n - 1)
return Tn[0][0]
def main():
print(fibonacci(10))
print(fibonacci(10**9))
if __name__ == '__main__':
main()
4. Phương pháp dựng ma trận cho các hệ thức truy hồi tổng quát
Nguyên lý lũy thừa ma trận không chỉ giới hạn ở Fibonacci. Bất kỳ hệ thức truy hồi tuyến tính dạng: \[F(n) = c_1 F(n-1) + c_2 F(n-2) + \dots + c_k F(n-k)\] đều có thể xây dựng ma trận chuyển trạng thái cấp \(K \times K\):
\[\begin{pmatrix} F(n) \\ F(n-1) \\ F(n-2) \\ \dots \\ F(n-k+1) \end{pmatrix} = \begin{pmatrix} c_1 & c_2 & c_3 & \dots & c_k \\ 1 & 0 & 0 & \dots & 0 \\ 0 & 1 & 0 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 & 0 \end{pmatrix} \begin{pmatrix} F(n-1) \\ F(n-2) \\ F(n-3) \\ \dots \\ F(n-k) \end{pmatrix}\]
Xử lý hệ thức có hằng số hoặc đa thức
Nếu hệ thức có thêm số hạng tự do, ví dụ: \[F(n) = 2 F(n-1) + 3 F(n-2) + 5\] Ta bổ sung thêm một trạng thái hằng số \(1\) vào vector trạng thái: \[V_n = \begin{pmatrix} F(n) \\ F(n-1) \\ 1 \end{pmatrix}\] Khi đó, ma trận chuyển trạng thái cấp \(3 \times 3\) sẽ là: \[T = \begin{pmatrix} 2 & 3 & 5 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}\] Bằng cách thêm các biến phụ này, bạn có thể biến đổi mọi bài toán quy hoạch động tuyến tính sang nhân ma trận để tăng tốc từ \(O(N)\) xuống \(O(K^3 \log N)\).
Bảng chạy tay chi tiết lũy thừa ma trận tính số Fibonacci
Để hiểu rõ cách lũy thừa nhị phân hoạt động trên ma trận, ta theo dõi từng bước tính số Fibonacci thứ 10: \(F(10) = 55\). Cần tính ma trận chuyển trạng thái \(T^9\) với \(T = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\).
Số mũ \(9\) được biểu diễn dưới dạng nhị phân là \(9 = (1001)_2 = 2^3 + 2^0\). Quá trình tính toán diễn ra qua 4 bước, mỗi bước xét một bit của số mũ:
| Bước | Số mũ hiện tại | Bit bật | Ma trận cơ sở hiện tại | Ma trận kết quả tích lũy |
|---|---|---|---|---|
| Khởi tạo | 9 | - | \(T = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) | \(res = I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\) |
| Bước 1 | 9 (Lẻ) | Có (\(2^0\)) | \(T^1 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) | \(res = res \times T^1 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) |
| Bình phương | - | - | \(T^2 = T \times T = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\) | \(res\) giữ nguyên |
| Bước 2 | 4 (Chẵn) | Không | \(T^2 = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\) | \(res\) giữ nguyên |
| Bình phương | - | - | \(T^4 = T^2 \times T^2 = \begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix}\) | \(res\) giữ nguyên |
| Bước 3 | 2 (Chẵn) | Không | \(T^4 = \begin{pmatrix} 5 & 3 \\ 3 & 2 \end{pmatrix}\) | \(res\) giữ nguyên |
| Bình phương | - | - | \(T^8 = T^4 \times T^4 = \begin{pmatrix} 34 & 21 \\ 21 & 13 \end{pmatrix}\) | \(res\) giữ nguyên |
| Bước 4 | 1 (Lẻ) | Có (\(2^3\)) | \(T^8 = \begin{pmatrix} 34 & 21 \\ 21 & 13 \end{pmatrix}\) | \(res = res \times T^8 = \begin{pmatrix} 55 & 34 \\ 34 & 21 \end{pmatrix}\) |
Cuối cùng, nhân ma trận kết quả với vector cơ sở \(\begin{pmatrix} F(1) \\ F(0) \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\):
\[\begin{pmatrix} F(10) \\ F(9) \end{pmatrix} = \begin{pmatrix} 55 & 34 \\ 34 & 21 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 55 \\ 34 \end{pmatrix}\]
Kết quả \(F(10) = 55\) và \(F(9) = 34\) được tìm ra hoàn toàn chính xác sau 3 lần bình phương và 2 lần nhân vào kết quả (lần nhân đầu chỉ là \(I \times T\)). Hàm power() ở mục 3 còn bình phương thêm một lần sau bit cuối (ra \(T^{16}\), không dùng tới), nên với số mũ 9 nó gọi multiply() tổng cộng 6 lần.
Bốn lỗi lập trình thường gặp khi nhân ma trận
-
Thứ tự vòng lặp i-j-k làm giảm hiệu năng CPU: Khi nhân hai ma trận kích thước \(K \times K\), việc duyệt theo thứ tự truyền thống
i-j-kkhiến phần tửB[k][j]bị nhảy ô nhớ liên tục theo cột. Đổi thứ tự thànhi-k-jgiúp đọc tuần tự theo hàng của ma trậnB, tận dụng tối đa bộ nhớ đệm CPU Cache Line và tăng tốc thực thi từ 3 đến 5 lần. -
Tràn số trong vòng lặp nhân dồn: Trong C++, phép nhân
A[i][k] * B[k][j]có thể vượt quá kiểu số nguyên 32-bit nếu giá trị ma trận lên tới \(10^9\). Bắt buộc phải ép kiểu1LLvà thực hiện phép chia lấy dư modulo thường xuyên để tránh tràn số. -
Xác định sai số mũ ma trận: Để tính số hạng thứ \(N\) của dãy số, nhiều bạn nâng ma trận lên lũy thừa \(N\) thay vì \(N - 1\). Với \(N = 1\), ma trận lũy thừa \(1 - 1 = 0\) phải là ma trận đơn vị \(I\). Nếu nâng lên lũy thừa 1 sẽ cho ra kết quả của \(F(2)\) thay vì \(F(1)\).
-
Xử lý số hạng tự do trong hệ thức truy hồi: Khi gặp hệ thức có hằng số cộng thêm như \(F(n) = F(n-1) + F(n-2) + C\), ma trận chuyển trạng thái cần mở rộng thêm một hàng và một cột phụ với giá trị 1 ở góc dưới để duy trì hằng số qua các bước lũy thừa.
Luyện ngay trên Big-O Coding
Hãy thử sức với các bài toán dùng ma trận và tư duy lũy thừa nhị phân (nhảy nhị phân) trên hệ thống Big-O Coding:
Tại sao khi cài đặt nhân ma trận, thứ tự các vòng lặp nên là i-k-j thay vì i-j-k?
Trong ngôn ngữ C/C++, mảng hai chiều được lưu trữ liên tục theo hàng (Row-Major Order). Khi đặt vòng lặp k ở giữa và j ở trong cùng, phần tử B[k][j] và C[i][j] được đọc ghi liên tục trên cùng một dòng bộ nhớ đệm (CPU Cache Line). Điều này giúp tối ưu hóa phần cứng và chạy nhanh hơn gấp 3 đến 5 lần so với thứ tự i-j-k truyền thống.
Định lý Cayley-Hamilton và Thuật toán Berlekamp-Massey có liên hệ gì với nhân ma trận?
Khi kích thước ma trận \(K\) lớn (\(K \ge 100\)), phép nhân ma trận \(O(K^3 \log N)\) trở nên quá chậm. Bằng cách sử dụng đa thức đặc trưng (Characteristic Polynomial) và định lý Cayley-Hamilton kết hợp thuật toán chia đa thức (Kitamasa / Bostan-Mori), ta có thể tính số hạng thứ \(N\) chỉ trong thời gian \(O(K^2 \log N)\) hoặc \(O(K \log K \log N)\).
Nguồn tham khảo
- CP-Algorithms - Binary Exponentiation and Matrix Exponentiation - Hướng dẫn chi tiết kỹ thuật nhân ma trận và lũy thừa nhị phân
- VNOI Wiki - Nhân ma trận - Chuyên đề nâng cao về ma trận trong quy hoạch động và đồ thị
- USACO Guide - Matrix Exponentiation - Các dạng bài tập thi đấu quốc tế áp dụng lũy thừa ma trận
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


