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ài dễ quá :3
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.