Tổng Fibonaci

Xem PDF
Tác giả:
Small
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


  • 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!


    • 0
      longdegea11    11:40 p.m. 7 Tháng 6, 2023 ← chỉnh sửa 2

      Theo như mình thấy thì: Si = F(i + 3) - 1 nếu nhân ma trận, còn theo công thức thì đúng rồi
      .


      • -4
        villeclaude    4:03 p.m. 25 Tháng 4, 2023

        nhân như nào hả bạn ?

      1 bình luận nữa