NTUCoder - Bài tập

FIBO2 - Fibonaci

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: phamhuuthien

Xét dãy số Fibonaci {F_n} theo định nghĩa:

F₁ = F₂ = 1

F_n = F_{n - 1} + F_{n - 2} với mọi n > 2

Cho n, hãy tính F_n và đưa ra số dư của F_n chia cho (10⁶ + 7)

Dữ liệu vào: n (0 < n ≤ 10¹⁵)

Dữ liệu ra: một số nguyên – số dư tìm được.

Ví dụ

input

1

output

1
input

11

output

89
input

121

output

146484

Bài tập này yêu cầu độ phức tạp từ O(log n) trở xuống.

Bài tập mới

Coder tích cực

Back to Top