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
n + 1 mà đề bịp=))
Để 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.
f(0) = f(1) = 1 mà bạn, chắc bạn nhầm rằng f(0) = 0.