Hướng dẫn giải của Lũy thừa ma trận
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tính lũy thừa ma trận bậc n của một ma trận vuông A cấp m. Với m lên tới 100 và n lên tới 10^18, ta cần tính B = A^n. Kết quả cần lấy dư cho 10^9 + 7 cho mỗi phần tử. Do n rất lớn, các phương pháp lặp thông thường (nhân ma trận n lần) sẽ không khả thi về thời gian.
Các cách tiếp cận
Cách Nhân ma trận lặp lại (Binary Exponentiation)
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1e9 + 7;
struct Matrix {
int size;
vector<vector<long long>> mat;
Matrix(int s = 0) : size(s), mat(s, vector<long long>(s, 0)) {}
};
Matrix multiply(const Matrix& A, const Matrix& B) {
Matrix C(A.size);
for (int i = 0; i < A.size; ++i) {
for (int j = 0; j < A.size; ++j) {
for (int k = 0; k < A.size; ++k) {
C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
}
}
}
return C;
}
Matrix power(Matrix A, long long n) {
Matrix Res(A.size);
for (int i = 0; i < A.size; ++i) {
Res.mat[i][i] = 1;
}
while (n > 0) {
if (n % 2 == 1) {
Res = multiply(Res, A);
}
A = multiply(A, A);
n /= 2;
}
return Res;
}
int main() {
int m;
long long n;
cin >> m >> n;
Matrix A(m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
cin >> A.mat[i][j];
A.mat[i][j] %= MOD;
}
}
Matrix B = power(A, n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
cout << B.mat[i][j] << (j == m - 1 ? "" : " ");
}
cout << "\n";
}
return 0;
}
- Time Complexity: O(m^3 * log n)
- Space Complexity: O(m^2)
Đây là phương pháp chuẩn để tính lũy thừa với số mũ lớn. Thay vì nhân ma trận n lần, ta sử dụng thuật toán bình phương liên tục (Binary Exponentiation).
- Khởi tạo: Ma trận kết quả
Reskhởi tạo bằng ma trận đơn vị (bậc 1 trên đường chéo). - Lặp: Khi n > 0:
- Nếu n lẻ (n % 2 == 1):
Res = Res * A(nhân ma trận hiện tại với kết quả). - Cập nhật
A = A * A(bình phương ma trận cơ sở). - Chia đôi n (n /= 2).
- Nếu n lẻ (n % 2 == 1):
- Nhân ma trận: Hàm nhân ma trận thực hiện phép nhân ma trận vuông cấp m, với độ phức tạp O(m^3). Cần thực hiện khoảng log2(n) lần nhân.
Ví dụ: Tính A^13 (13 = 1101 binary).
- Res = I, A = A
- Bit 1 (dư 1): Res = I * A = A
- A = A^2
- Bit 0 (dư 0): Res không đổi
- A = A^4
- Bit 1 (dư 1): Res = A * A^4 = A^5
- A = A^8
- Bit 1 (dư 1): Res = A^5 * A^8 = A^13
Phương pháp này tối ưu vì chỉ mất O(log n) bước nhân.
Cách Đệ quy có nhớ (Recursive Exponentiation)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int m;
struct Matrix {
int n;
vector<vector<int>> x;
Matrix(int _n = 0) {
n = _n;
x.resize(n, vector<int>(n));
}
};
Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix c(m);
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k < m; ++k)
c.x[i][j] = (c.x[i][j] + 1LL * a.x[i][k] * b.x[k][j]) % MOD;
return c;
}
Matrix Bpow(Matrix T, long long n) {
Matrix I(m);
for (int i = 0; i < m; ++i) I.x[i][i] = 1;
if (n == 0) return I;
if (n == 1) return T;
Matrix half = Bpow(T, n / 2);
if (n % 2 == 0) return half * half;
return half * half * T;
}
int main() {
long long n;
cin >> m >> n;
Matrix A(m);
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j) {
cin >> A.x[i][j];
A.x[i][j] %= MOD;
}
Matrix B = Bpow(A, n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) cout << B.x[i][j] << " ";
cout << "\n";
}
return 0;
}
- Time Complexity: O(m^3 * log n)
- Space Complexity: O(m^2 * log n)
Đây là cách tiếp cận đệ quy của thuật toán bình phương liên tục.
Đề bài cơ bản:
- Nếu n = 0, trả về ma trận đơn vị.
- Nếu n = 1, trả về ma trận chính nó.
Đệ quy:
- Chia n thành 2 nửa:
half = Bpow(T, n/2). - Nếu n chẵn: trả về
half * half. - Nếu n lẻ: trả về
half * half * T.
- Chia n thành 2 nửa:
So với cách lặp, đệ quy dễ hiểu hơn nhưng tốn bộ nhớ hơn do độ sâu của stack (O(log n)). Tuy nhiên, trong thực tế với n lên tới 10^18, log2(n) ≈ 60, nên mức độ đệ quy này hoàn toàn an toàn và không gây tràn stack.
Cách Tối ưu lưu trữ (Fixed-size Array)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MAX_M = 105;
struct Matrix {
int x[MAX_M][MAX_M];
int size;
Matrix(int s = 0) : size(s) {
memset(x, 0, sizeof(x));
}
};
Matrix multiply(const Matrix& A, const Matrix& B) {
Matrix C(A.size);
for (int i = 0; i < A.size; ++i) {
for (int j = 0; j < A.size; ++j) {
long long sum = 0;
for (int k = 0; k < A.size; ++k) {
sum += (long long)A.x[i][k] * B.x[k][j];
if (sum >= 1LL * MOD * MOD) sum %= MOD;
}
C.x[i][j] = sum % MOD;
}
}
return C;
}
Matrix power(Matrix A, long long n) {
Matrix Res(A.size);
for (int i = 0; i < A.size; ++i) Res.x[i][i] = 1;
while (n > 0) {
if (n & 1) Res = multiply(Res, A);
A = multiply(A, A);
n >>= 1;
}
return Res;
}
int main() {
int m;
long long n;
cin >> m >> n;
Matrix A(m);
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j) {
cin >> A.x[i][j];
A.x[i][j] %= MOD;
}
Matrix B = power(A, n);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) cout << B.x[i][j] << " ";
cout << "\n";
}
return 0;
}
- Time Complexity: O(m^3 * log n)
- Space Complexity: O(m^2)
Đây là phiên bản tối ưu hóa bộ nhớ và tốc độ của phương pháp Binary Exponentiation.
Tối ưu hóa chính:
- Mảng tĩnh: Thay vì dùng
vector<vector<long long>>, dùng mảng 2 chiều tĩnhint x[MAX_M][MAX_M]. Điều này giúp dữ liệu lưu liên tục trong bộ nhớ, giảm thời gian truy cập bộ nhớ (cache locality) và loại bỏ overhead của vector.
Kiểu số nguyên: Dùng
intthay vìlong longcho các phần tử ma trận (sau khi lấy dư) để tiết kiệm bộ nhớ và tăng tốc độ.Tối ưu phép nhân:
- Dùng biến
long longtạm tính tổng để tránh tràn số khi nhân 2 số lớn. - Kiểm tra điều kiện
sum >= 1LL * MOD * MODđể giảm số lần gọi modulo, tăng tốc độ đáng kể.
- Dùng biến
Bitwise operations: Dùng
n & 1thay vìn % 2vàn >>= 1thay vìn /= 2để tối ưu CPU.
Đây là cách thường dùng trong các kỳ thi lập trình cạnh tranh để đạt hiệu suất cao nhất.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(m^3 * log n) | O(m^2) | Nhân ma trận lặp lại (Binary Exponentiation) |
| 2 | O(m^3 * log n) | O(m^2 * log n) | Đệ quy có nhớ (Recursive Exponentiation) |
| 3 | O(m^3 * log n) | O(m^2) | Tối ưu lưu trữ (Fixed-size Array) |
Bài học kinh nghiệm
- Phương pháp Binary Exponentiation (bình phương liên tục) là chìa khóa để giải quyết bài toán với số mũ lớn O(10^18). Nó giảm độ phức tạp từ O(n) xuống O(log n).
- Phép nhân ma trận kết hợp với bình phương liên tục cho phép tính A^n chỉ với O(log n) lần nhân ma trận, mỗi lần tốn O(m^3).
Lỗi thường gặp
- Tràn số (Integer Overflow): Khi nhân 2 phần tử ma trận, giá trị có thể lên tới (10^9)^2 = 10^18. Cần dùng kiểu dữ liệu 64-bit (long long) cho biến trung gian khi tính toán trước khi lấy modulo.
- Quên ma trận đơn vị: Ma trận kết quả ban đầu phải là ma trận đơn vị (bậc 1), không phải ma trận 0. Nếu không, kết quả sẽ sai khi n=0 hoặc trong các bước nhân.
- Độ phức tạp không gian: Nếu dùng đệ quy không tail-call optimization, độ sâu stack O(log n) có thể gây tràn stack với n rất lớn (mặc dù 60 levels là an toàn).
Bình luận