Hướng dẫn giải của Dãy con
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
, , ,
Editorial for ptit044: Dãy con
Hiểu bài toán
Xét một dãy số U với công thức truy hồi: U0 = -1, U1 = 3, và U{n+1} = 5*Un - 6*U{n-1}. Với n lớn (đến 10^11), cần tính Un theo modulo 10^9 + 7. Đây là bài toán tìm hạng tử thứ n của dãy số tuyến tính.
Các cách tiếp cận
Cách Mãnh liệt (Quy hoạch động)
// Phân tích: U_{n} = 5*U_{n-1} - 6*U_{n-2}
// Duyệt từ 2 đến n, lưu 2 giá trị trước đó
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int main() {
long long n;
cin >> n;
if (n == 0) { cout << -1; return 0; }
if (n == 1) { cout << 3; return 0; }
long long u0 = -1, u1 = 3, un;
for (long long i = 2; i <= n; i++) {
un = (5 * u1 - 6 * u0) % mod;
if (un < 0) un += mod;
u0 = u1;
u1 = un;
}
cout << u1;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Giải pháp này dựa trên định nghĩa trực tiếp của dãy số. Ta sử dụng hai biến để lưu U{n-1} và U{n-2}, cập nhật liên tục trong vòng lặp từ 2 đến n. Tuy nhiên, với n lên tới 10^11, cách này sẽ quá thời gian cho phép vì số bước lặp quá lớn.
Cách Công thức tổng quát (Ma trận)
// U_n = 5^n - 2^n
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
long long powmod(long long a, long long b) {
long long res = 1;
a %= mod;
while (b > 0) {
if (b % 2 == 1) res = (res * a) % mod;
a = (a * a) % mod;
b /= 2;
}
return res;
}
int main() {
long long n;
cin >> n;
long long ans = (powmod(5, n) - powmod(2, n)) % mod;
if (ans < 0) ans += mod;
cout << ans;
}
- Time Complexity: O(log n)
- Space Complexity: O(1)
Đặc trưng phương trình truy hồi là x^2 - 5x + 6 = 0 => x = 5, 2. Dạng tổng quát là Un = A*5^n + B*2^n. Thay điều kiện ban đầu: U0 = -1 = A + B, U1 = 3 = 5A + 2B => A = 1, B = -1. Vậy Un = 5^n - 2^n. Ta chỉ cần tính lũy thừa nhanh modulo.
Cách Nâng cao (Ma trận lũy thừa)
// Sử dụng ma trận để nhân đôi
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1e9 + 7;
typedef vector<vector<long long>> Matrix;
Matrix multiply(Matrix A, Matrix B) {
int n = A.size();
Matrix C(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
return C;
}
Matrix power(Matrix A, long long p) {
int n = A.size();
Matrix res(n, vector<long long>(n, 0));
for (int i = 0; i < n; i++) res[i][i] = 1;
while (p > 0) {
if (p & 1) res = multiply(res, A);
A = multiply(A, A);
p >>= 1;
}
return res;
}
int main() {
long long n;
cin >> n;
if (n == 0) { cout << (mod - 1) % mod; return 0; }
if (n == 1) { cout << 3; return 0; }
Matrix T(2, vector<long long>(2));
T[0][0] = 5; T[0][1] = -6;
T[1][0] = 1; T[1][1] = 0;
Matrix Tn = power(T, n - 1);
long long res = (Tn[0][0] * 3 + Tn[0][1] * (mod - 1)) % mod;
cout << res;
}
- Time Complexity: O(log n)
- Space Complexity: O(1)
Thay vì tìm công thức tổng quát, ta có thể sử dụng ma trận chuyển trạng thái. Vector [Un, U{n-1}] = Ma trận * [U{n-1}, U{n-2}]. Ma trận T là [[5, -6], [1, 0]]. T^n-1 * [U1, U0] sẽ cho [Un, U{n-1}]. Cách này tổng quát hơn và không cần tìm công thức tổng quát thủ công.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(1) | Mãnh liệt (Quy hoạch động) |
| 2 | O(log n) | O(1) | Công thức tổng quát (Ma trận) |
| 3 | O(log n) | O(1) | Nâng cao (Ma trận lũy thừa) |
Bài học kinh nghiệm
- Phương trình đặc trưng x^2 - 5x + 6 = 0 có nghiệm là 5 và 2, dẫn đến công thức tổng quát U_n = 5^n - 2^n.
- Với n lớn, cần sử dụng thuật toán lũy thừa nhanh (Binary Exponentiation) để tính kết quả trong thời gian O(log n).
Lỗi thường gặp
- Quên xử lý số âm sau khi trừ các kết quả modulo (ví dụ: (5^n - 2^n) có thể âm). Cần cộng thêm mod trước khi lấy modulo cuối cùng.
- Sai công thức tổng quát nếu tính nhầm nghiệm của phương trình đặc trưng hoặc sai hệ số.
Bình luận
ủa trớt quớt ko x^2 - 5x + 6 = 0 <=> x = 2 và x = 3, số 5 đâu ra trời, đã vậy 5^n - 2^n có thể âm nữa chứ