Matrix Exponentiation - Fibonacci
View as PDF
Submit solution
Points:
0.40
Time limit:
0.25s
Memory limit:
256M
Input:
stdin
Output:
stdout
Suggester:
Problem source:
Problem type
Allowed languages
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,…)~.
Comments
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.