Matrix Exponentiation - Fibonacci
Xem dạng PDF
Gửi bài giải
Điểm:
0,40
Giới hạn thời gian:
0.25s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Người đăng:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Hãy tìm phần dư của phép chia lấy dư số Fibonacci thứ ~n~ cho ~10^9+7~.
Số Fibonacci thứ ~n~ ~(F_n)~ được xác định bởi dãy truy hồi sau:
~F_0 = 0, F_1 = 1~
~F_n = F_{n-1} + F_{n-2}\ (\forall n \geq 2)~
Input
Gồm ~1~ dòng chứa số nguyên ~n~ ~(0 \leq n \leq 10^{18})~.
Output
Phần dư của phép chia ~F_n~ cho ~10^9 + 7~.
Sample 1
Input
3
Output
2
Sample 2
Input
6
Output
8
Sample 3
Input
50
Output
586268941
~F_{50} = 12586269025 \equiv 586268941~ ~(mod ~ ~10^9 + 7)~.
Note
Một vài số hạng đầu tiên của dãy số Fibonacci là ~(0,1,1,2,3,5,8,13,…)~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.