Hướng dẫn giải của Dãy số
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
Cho một dãy số $(an)$ được định nghĩa với các giá trị ban đầu $a1 = 1, a2 = 2, a3 = 3$ và công thức truy hồi $an = a{n-3} - 2a{n-2} + 3a{n-1}$ cho mọi $n \ge 4$. Yêu cầu tính giá trị $a{ni}$ cho $m$ truy vấn với $ni$ lên tới $10^{18}$ và in ra phần dư của chúng khi chia cho $10^9 + 7$. Do $ni$ rất lớn, các phương pháp duyệt tuần tự sẽ không thể thực hiện được trong thời gian cho phép.
Các cách tiếp cận
Cách Ma trận lũy thừa (Matrix Exponentiation)
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1e9 + 7;
const int SIZE = 3;
struct Matrix {
long long mat[SIZE][SIZE];
};
Matrix multiply(Matrix A, Matrix B) {
Matrix C;
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
C.mat[i][j] = 0;
for (int k = 0; k < SIZE; ++k) {
C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
}
}
}
return C;
}
Matrix power(Matrix Base, long long Exp) {
Matrix Res;
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
Res.mat[i][j] = (i == j);
}
}
while (Exp > 0) {
if (Exp % 2 == 1) Res = multiply(Res, Base);
Base = multiply(Base, Base);
Exp /= 2;
}
return Res;
}
long long solve(long long n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 3;
Matrix T;
// Ma trận chuyển trạng thái từ [a_{n-1}, a_{n-2}, a_{n-3}] sang [a_n, a_{n-1}, a_{n-2}]
// a_n = 3*a_{n-1} - 2*a_{n-2} + 1*a_{n-3}
T.mat[0][0] = 3; T.mat[0][1] = -2; T.mat[0][2] = 1;
T.mat[1][0] = 1; T.mat[1][1] = 0; T.mat[1][2] = 0;
T.mat[2][0] = 0; T.mat[2][1] = 1; T.mat[2][2] = 0;
// T^(n-3) * [a3, a2, a1]^T = [a_n, a_{n-1}, a_{n-2}]^T
T = power(T, n - 3);
// a_n là phần tử đầu tiên của ma trận kết quả nhân với vector cơ sở [3, 2, 1]
long long res = (T.mat[0][0] * 3 + T.mat[0][1] * 2 + T.mat[0][2] * 1) % MOD;
if (res < 0) res += MOD;
return res;
}
int main() {
int m;
cin >> m;
while(m--) {
long long n;
cin >> n;
cout << solve(n) << " ";
}
return 0;
}
- Time Complexity: O(log n) cho mỗi truy vấn
- Space Complexity: O(1)
Phương pháp này biến đổi bài toán truy hồi tuyến tính bậc 3 thành bài toán lũy thừa ma trận. Ta cần tìm ma trận chuyển trạng thái $T$ sao cho $T \times [a{n-1}, a{n-2}, a{n-3}]^T = [an, a{n-1}, a{n-2}]^T$. Dựa vào công thức $an = 3a{n-1} - 2a{n-2} + a{n-3}$, ta suy ra ma trận $T = \begin{pmatrix} 3 & -2 & 1 \ 1 & 0 & 0 \ 0 & 1 & 0 \end{pmatrix}$. Khi đó $T^{n-3} \times [a3, a2, a1]^T = [an, a{n-1}, a{n-2}]^T$. Để tính $a_n$, ta chỉ cần tính $T^{n-3}$ bằng phép nhân ma trận và lũy thừa nhanh, sau đó lấy phần tử đầu tiên của ma trận nhân với vector ban đầu. Do $n$ có thể lên tới $10^{18}$, độ phức tạp $O(\log n)$ cho mỗi truy vấn là hoàn toàn khả thi.
Cách Đệ quy có nhớ (Memoization)
// Lưu ý: Phương pháp này chỉ hiệu quả với n nhỏ, không khả thi với n <= 10^18
#include <iostream>
#include <map>
using namespace std;
const long long MOD = 1e9 + 7;
map<long long, long long> memo;
long long solve(long long n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (n == 3) return 3;
if (memo.count(n)) return memo[n];
long long res = (solve(n-3) - 2 * solve(n-2) + 3 * solve(n-1)) % MOD;
if (res < 0) res += MOD;
return memo[n] = res;
}
int main() {
int m;
cin >> m;
while(m--) {
long long n;
cin >> n;
cout << solve(n) << " ";
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là cách tiếp cận trực quan nhất, cài đặt lại chính xác công thức truy hồi với việc lưu lại các kết quả đã tính (memoization) để tránh tính toán lại. Tuy nhiên, độ phức tạp phụ thuộc trực tiếp vào giá trị $n$, do $n$ lớn ($10^{18}$) nên phương pháp này không thể chạy được trong thời gian giới hạn. Nó chỉ dùng để minh họa logic bài toán cho các dữ liệu nhỏ.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(log n) cho mỗi truy vấn | O(1) | Ma trận lũy thừa (Matrix Exponentiation) |
| 2 | O(n) | O(n) | Đệ quy có nhớ (Memoization) |
Bài học kinh nghiệm
- Bài toán truy hồi tuyến tính có thể giải quyết nhanh chóng bằng ma trận lũy thừa, biến độ phức tạp từ $O(n)$ xuống $O(k^3 \log n)$ với $k$ là bậc của truy hồi (ở đây $k=3$).
- Cần xử lý số âm trong quá trình tính toán modulo bằng cách cộng thêm MOD nếu kết quả âm, vì phép chia số nguyên trong C++ có thể trả về số âm.
Lỗi thường gặp
- Quên xử lý số âm sau khi thực hiện phép trừ trong công thức truy hồi hoặc khi tính toán trong ma trận (vì ma trận có thể chứa số âm).
- Sử dụng sai kích thước ma trận hoặc sai chỉ số khi truy cập phần tử ma trận.
- Lỗi tràn số (integer overflow) khi nhân hai số lớn trước khi chia lấy dư, cần ép kiểu sang
long longvà lấy dư sau mỗi phép nhân.
Bình luận