I. Tổng quan
Trong lập trình thi đấu, đôi khi ta gặp các bài toán tìm số hạng thứ của dãy số hoặc đếm số cách thực hiện một công việc với bước.
Nếu : Dùng dp thông thường với độ phức tạp .
Nếu : Cách sẽ bị TLE. Ta cần phương pháp bằng cách sử dụng nhân ma trận (với là kích thước ma trận).
II. Các bước thực hiện
Bước 1: Tìm công thức truy hồi (Subtask nhỏ)
Trước khi nghĩ đến ma trận, phải giải được bài toán bằng dp thường (với nhỏ). Mục tiêu là tìm ra mối quan hệ tuyến tính giữa trạng thái hiện tại và các trạng thái trước đó.
Công thức thường có dạng:
Lưu ý: Kỹ thuật này chỉ áp dụng hiệu quả khi số lượng trạng thái phụ thuộc là nhỏ (thường ).
Bước 2: Xây dựng Ma trận chuyển trạng thái (Transition Matrix)
Ta cần tìm một ma trận (ma trận chuyển vị) và một vector cột (ma trận trạng thái) sao cho:
Từ đó suy ra công thức tổng quát:
Cách xây dựng:
Xác định Vector trạng thái (): Liệt kê các giá trị cần thiết để tính ra trạng thái tiếp theo.
Xác định Vector kết quả (): Là vector ở bước tiếp theo.
Điền ma trận : Dựa vào công thức truy hồi để điền các hệ số vào ma trận .
Bước 3: Lũy thừa ma trận (Binary Exponentiation)
Sử dụng thuật toán lũy thừa nhị phân (tương tự như tính ) nhưng áp dụng cho phép nhân ma trận để tính với độ phức tạp .
III. Ví dụ kinh điển: Dãy Fibonacci
Bài toán: Tính số Fibonacci thứ (), chia dư cho .
Công thức: .
Phân tích theo các bước:
1. Vector trạng thái ():
Để tính , ta cần và .
Vậy vector cột sẽ là:
2. Vector mục tiêu ():
Khi tăng lên một bước, ta cần có:
3. Tìm ma trận chuyển vị :
Ta cần tìm ma trận sao cho:
Dựa vào công thức truy hồi:
Hàng 1: Hệ số là 1 và 1.
Hàng 2: Hệ số là 1 và 0.
Vậy ma trận chuyển vị là:
Công thức cuối cùng:
(Giả sử ).
Mã giải (c++)
struct matrix {
int n;
vector<vector<ll>> f;
matrix() {}
matrix(int n) : n(n), f(n, vector<ll>(n, 0)) {}
matrix identity() {
matrix res(n);
FOR(i, 0, n) res.f[i][i] = 1;
return res;
}
matrix operator *(const matrix& other) {
matrix res(n);
FOR(i, 0, n) {
FOR(k, 0, n) {
if (!f[i][k]) continue;
FOR(j, 0, n) {
res.f[i][j] += f[i][k] * other.f[k][j] % mod;
res.f[i][j] %= mod;
}
}
}
return res;
}
matrix operator ^(ll b) {
matrix res = identity();
matrix a = (*this);
while (b) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
};
int main(void) {
ll n; cin >> n;
matrix base(2);
base.f = { {1, 0}, {0, 0} };
matrix transit(2);
transit.f = { {1, 1}, {1, 0} };
matrix res = (transit ^ (n - 1)) * base;
cout << res.f[0][0];
}IV. Các mô hình nâng cao
Dạng 1: Có hằng số cộng thêm
Ta thêm con số vào vector trạng thái để giữ giá trị hằng số .
Vector:
Ma trận chuyển:
Dạng 2: Tính tổng dồn (Prefix Sum)
Tính .
Ta có . Ta thêm vào vector trạng thái.
Vector:
Ma trận chuyển (kết hợp logic của ):
(Giải thích hàng 1: ).