Hướng dẫn giải của [Free Contest 06] FIBONACCI
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Hướng dẫn giải
Tính F(n) mod 10^9+7 với F(1) = F(2) = 1. Với n lên tới 10^{12} không thể đi từng bước.
Sub 1: Cộng dồn trực tiếp — ~O(n)~, dùng khi ~n \le 10^6~
Giữ hai số liên tiếp và cộng dồn theo modulo cho đến F(n). Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2 (đầy đủ): Nhân đôi (fast doubling) — ~O(\log n)~
Dùng F(2k) = F(k) (2F(k+1) - F(k)) và F(2k+1) = F(k)^2 + F(k+1)^2 để tính đệ quy cặp (F(k), F(k+1)) trong O(\log n). Mọi phép toán lấy modulo, phép trừ được cộng thêm MOD để không âm. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc n. Nếu n \le 10^6 gọi sub1, ngược lại gọi sub3 (nhân đôi).
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
long long n;
// Sub 1: n <= 50, cong don truc tiep. O(n)
void sub1() {
long long a = 1, b = 1; // F(1), F(2)
for (long long i = 3; i <= n; i++) {
long long c = (a + b) % MOD;
a = b; b = c;
}
cout << (n <= 2 ? 1 : b) << "\n";
}
// Sub 2: n <= 10^6, van cong don nhung voi modulo. O(n)
void sub2() {
sub1();
}
// Sub 3 (day du): nhan doi (fast doubling). Voi n, tinh (F(n), F(n+1)) trong O(log n):
// F(2k) = F(k) * (2F(k+1) - F(k)), F(2k+1) = F(k)^2 + F(k+1)^2.
pair<long long, long long> fib(long long k) {
if (k == 0) return {0, 1};
auto [a, b] = fib(k >> 1);
long long c = a * ((2 * b % MOD - a + MOD) % MOD) % MOD;
long long d = (a * a % MOD + b * b % MOD) % MOD;
if (k & 1) return {d, (c + d) % MOD};
return {c, d};
}
void sub3() {
cout << fib(n).first << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
if (n <= 1000000) sub1();
else sub3();
return 0;
}
Bình luận