BIGFIBO - Dãy số Fibonacci
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Dãy số Fibonacci được định nghĩa bởi công thức:
$$\left\{ \begin{array}{l}{F_0} = {F_1} = 1\\{F_n} = {F_{n - 1}} + {F_{n - 2}},\forall n \ge 2\end{array} \right.$$
Yêu cầu: Cho số nguyên không âm ~n~, hãy tính ~F_n~.
Input
- Một dòng duy nhất chứa số nguyên không âm ~n~.
Giới hạn:
- ~0 ≤ n ≤ 10^{18}~.
Output
- Một dòng duy nhất chứa số nguyên là phần dư của ~F_n~ khi chia cho ~10^9 + 7~.
Sample
Input #1
10
Output #1
89
Input #2
45
Output #2
836311896
Problem source: Chuyên Sơn La Online Judge
Bình luận
Để AC bài này (với cách làm của mình): Ta sử dụng phương pháp tìm số Fib thứ n = Luỹ thừa nhị phân kết hợp với nhân ma trận O(log(n)) (trên mạng có nhé các bạn có thể tìm hiểu). Còn code tuyến tính O(n) sẽ bị TLE.
anh chi nao code mau C++ giup em dc ko a em bi tle
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
f(0) = f(1) = 1 mà bạn, chắc bạn nhầm rằng f(0) = 0.