Nhân Ma Trận Lũy Thừa Nhanh O(K³ log N)

Buổi 59 — Lũy thừa ma trận Dynamic Programming Mathematics
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
matrix
Submissions
Đề 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
Draft saved