FIBO4 - 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 {Fn} theo định nghĩa:

F1 = F2 = 1

Fn = Fn - 1 + Fn - 2 với mọi n > 2

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

Dữ liệu vào: n (0 < n ≤ 106)

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(n) trở xuống.

Back to Top