Tổng Fibonaci

Xem PDF



Tác giả:
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Xét dãy số Fibonacci \({Fn}\) theo định nghĩa:

  • \(𝐹_0=𝐹_1=1\)
  • \(𝐹_n=𝐹_{n-1}+𝐹_{n-2}\ ∀𝑛>1\)

Yêu cầu: Cho số \(𝒏\), hãy tính tổng \(𝑆=𝐹_0+𝐹_1+𝐹_2+⋯+𝐹_𝑛\) và đưa ra số dư của \(S\) chia cho (\(10^9+7\)).

Input

  • Chỉ một dòng duy nhất ghi số nguyên dương \(n\) (\(𝑛≤10^{15}\)).

Output

  • Ghi một số nguyên \(S\) – số dư tìm được.

Example

Test 1

Input
3    
Output
7
Note
  • \(S = 1+1+2+3\)

Test 1

Input
5    
Output
20
Note
  • \(S = 1+1+2+3+5+8\)

Nguồn: CĐ DHBB


Bình luận


  • 1
    nhuttruong2k9 10:29 p.m. 15 Tháng 1, 2024

    nhân ma trận tìm số fibo thứ n+3 rồi lấy kết quả -1


    • 6
      huyhau6a2 6:27 p.m. 13 Tháng 12, 2022

      Mình xin phép trình bày lời giải của bài toán này như sau:

      Gọi \(F_0=F_2-1\text{ }(F_2=2\) theo quy luật ban đầu\()\)
      Gọi \(S_i=F_0+F_1+F_2+...+F_i\)

      Ta có: \(S_0=F_0=F_2-1\)

      • \(S_1=S_0+F_1=F_2-1+F_1=(F_1+F_2)-1=F_3-1\)
      • \(S_2=S_1+F_2=F_3-1+F_2=(F_2+F_3)-1=F_4-1\)
      • \(...\)
      • \(S_i=S_{i-1}+F_i=F_{i+1}-1+F_i=(F_i+F_{i+1})-1=F_{i+2}-1\)

      Thực hiện quy nạp như trên, ta có công thức: \(S_i=F_{i+2}-1\)
      Đến đây chỉ cần thực hiện nhân ma trận là xong!

      2 phản hồi