Nhân Ma Trận Lũy Thừa Nhanh O(K³ log N)
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Đề bài
Dãy Fibonacci được định nghĩa bởi F(0) = 0, F(1) = 1, và F(n) = F(n-1) + F(n-2) với mọi n ≥ 2.
Cho số nguyên dương N (1 ≤ N ≤ 10^18), hãy tính F(N) mod (10^9 + 7) bằng kỹ thuật nhân ma trận lũy thừa nhị phân trong O(log N).
Dữ liệu vào (Input)
- Một dòng duy nhất chứa số nguyên dương
N(1 ≤ N ≤ 10^18).
Dữ liệu ra (Output)
- In ra
F(N) mod 1000000007.
Ví dụ mẫu
Sample Input 1
10
Sample Output 1
55
Sample Input 2
50
Sample Output 2
586268941
Community Discussion