Hướng dẫn giải của Dãy số Fibonacci
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 bigfibo: Dãy số Fibonacci
Hiểu bài toán
Bài toán yêu cầu tính số Fibonacci thứ n (với F0 = F1 = 1) và in ra kết quả lấy modulo 10^9 + 7. Dữ liệu đầu vào n có thể lên tới 10^18, nên các thuật toán thông thường chạy trong O(n) sẽ không thể thực hiện trong thời gian cho phép. Cần phải sử dụng các phương pháp tối ưu hơn như quy hoạch động kết hợp ma trận hoặc ma trận lũy thừa.
Các cách tiếp cận
Cách Quy hoạch động
#include <stdio.h>
#define MOD 1000000007
int main() {
long long n;
scanf("%lld", &n);
if (n == 0 || n == 1) {
printf("1\n");
return 0;
}
// Khởi tạo F[0] = 1, F[1] = 1
// Sử dụng hai biến để tiết kiệm bộ nhớ
long long a = 1, b = 1;
long long c;
for (long long i = 2; i <= n; i++) {
c = (a + b) % MOD;
a = b;
b = c;
}
printf("%lld\n", b);
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(1)
Phương pháp này sử dụng biến để lưu trữ hai số Fibonacci liên tiếp và lặp tính toán từ 2 đến n. Tuy nhiên, với n lên tới 10^18, vòng lặp này sẽ chạy quá lâu và không thể chấp nhận.
Cách Ma trận lũy thừa (Matrix Exponentiation)
#include <stdio.h>
#define MOD 1000000007ULL
typedef unsigned long long ull;
typedef struct {
ull a, b, c, d;
} Matrix;
// Nhân hai ma trận 2x2
Matrix multiply(Matrix m1, Matrix m2) {
Matrix result;
result.a = (m1.a * m2.a % MOD + m1.b * m2.c % MOD) % MOD;
result.b = (m1.a * m2.b % MOD + m1.b * m2.d % MOD) % MOD;
result.c = (m1.c * m2.a % MOD + m1.d * m2.c % MOD) % MOD;
result.d = (m1.c * m2.b % MOD + m1.d * m2.d % MOD) % MOD;
return result;
}
// Lũy thừa ma trận
Matrix power(Matrix base, ull exp) {
Matrix result = {1, 0, 0, 1}; // Ma trận đơn vị
while (exp > 0) {
if (exp % 2 == 1) {
result = multiply(result, base);
}
base = multiply(base, base);
exp /= 2;
}
return result;
}
int main() {
ull n;
scanf("%llu", &n);
if (n == 0 || n == 1) {
printf("1\n");
return 0;
}
// Ma trận cơ sở: [[1, 1], [1, 0]]
Matrix T = {1, 1, 1, 0};
// T^n sẽ là ma trận [[F_{n+1}, F_n], [F_n, F_{n-1}]]
// Ta cần F_n, nằm ở vị trí (0, 1)
Matrix res = power(T, n);
printf("%llu\n", res.b);
return 0;
}
- Time Complexity: O(log n)
- Space Complexity: O(1)
Sử dụng tính chất của ma trận: [[F{n+1}, Fn], [Fn, F{n-1}]] = [[1, 1], [1, 0]]^n. Bằng cách tính lũy thừa ma trận nhanh (nhân ma trận trong O(1) và lũy thừa trong O(log n)), ta có thể tìm ra F_n rất nhanh.
Cách Ma trận lũy thừa (Optimized)
#include <stdio.h>
const long long MOD = 1e9 + 7;
typedef struct {
long long a11, a12, a21, a22;
} Matrix;
Matrix nhan(Matrix x, Matrix y) {
Matrix z;
z.a11 = ((x.a11 * y.a11) % MOD + (x.a12 * y.a21) % MOD) % MOD;
z.a12 = ((x.a11 * y.a21) % MOD + (x.a12 * y.a22) % MOD) % MOD;
z.a21 = ((x.a21 * y.a11) % MOD + (x.a22 * y.a12) % MOD) % MOD;
z.a22 = ((x.a21 * y.a21) % MOD + (x.a22 * y.a22) % MOD) % MOD;
return z;
}
Matrix mu(Matrix x, long long n) {
if (n == 1) return x;
Matrix half = mu(x, n / 2);
if (n % 2 == 0) return nhan(half, half);
return nhan(nhan(half, half), x);
}
int main() {
long long t;
scanf("%lld", &t);
Matrix g;
g.a11 = 0;
g.a12 = 1;
g.a21 = 1;
g.a22 = 1;
if (t == 0) printf("1");
else {
// Ma trận g tương ứng với [[0, 1], [1, 1]]
// g^t tương ứng với [[F_{t-1}, F_t], [F_t, F_{t+1}]]
// Kết quả F_t nằm ở a12 (dòng 1 cột 2) hoặc a21 (dòng 2 cột 1)
// Code mẫu in res.a22, kiểm tra lại ma trận cơ sở.
// Nếu ma trận cơ sở là [[0, 1], [1, 1]],
// [[F1, F2], [F2, F3]] = [[1, 1], [1, 2]]
// g^1 = [[0, 1], [1, 1]].
// Ta cần F_n.
// Ma trận cơ sở B = [[1, 1], [1, 0]].
// Code mẫu dùng G = [[0, 1], [1, 1]].
// G^n = [[F_n, F_{n+1}], [F_{n+1}, F_{n+2}]].
// In ra a22 là F_{n+2}.
Matrix res = mu(g, t);
// Logic code mẫu: nếu t=1, res = g, a22 = 1 (F_1).
// Nếu t=2, res = g^2 = [[1, 1], [1, 2]], a22 = 2 (F_2).
// Vậy a22 là F_t.
printf("%lld", res.a22);
}
return 0;
}
- Time Complexity: O(log n)
- Space Complexity: O(log n) (do đệ quy)
Đây là cách cài đặt ma trận lũy thừa trực quan. Sử dụng ma trận cơ sở [[0, 1], [1, 1]]. Khi lũy thừa lên n, phần tử a22 của ma trận kết quả chính là F_n. Thuật toán chia để trị này có độ phức tạp logarithmic.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(1) | Quy hoạch động |
| 2 | O(log n) | O(1) | Ma trận lũy thừa (Matrix Exponentiation) |
| 3 | O(log n) | O(log n) (do đệ quy) | Ma trận lũy thừa (Optimized) |
Bài học kinh nghiệm
- Bài toán có tính lặp lại cao và có thể mô hình hóa bằng đại số ma trận.
- Với n lớn (10^18), thuật toán cần có độ phức tạp O(log n) để chạy trong thời gian giới hạn.
Lỗi thường gặp
- Sử dụng kiểu dữ liệu quá nhỏ (ví dụ: int) dẫn đến tràn số khi tính toán trước khi chia lấy dư.
- Lựa chọn sai ma trận cơ sở hoặc sai phần tử của ma trận lũy thừa làm kết quả.
- Quên xử lý trường hợp n = 0 hoặc n = 1.
Bình luận