Tổng Fibonaci

Xem PDF

Đ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

  • sondang0914 3:15 p.m. 29 Tháng 3, 2025

    các bạn sửa lỗi cho mình:
    a=int(input())
    sd=1
    sc=a+1//2-1
    ssh=(sc-sd)+1
    t=(sd+sc)*ssh+1
    print(t)

    • hbphuc2009 10:08 p.m. 5 Tháng 7, 2024

      Mình xin phép trình bày 1 cách giải bài này như sau:
      Ta có:
      F(0) + F(1) + F(2) + ... + F(n) = F(n+2) - 1 (Đẳng thức của dãy Fibonanci, các bạn có thể xem ở đây: https://vi.wikipedia.org/wiki/D%C3%A3y_Fibonacci)
      F(n + 1) = F(n) + F(n - 1)
      F(n + 2) = F(n) + F(n + 1) = F(n) + F(n) + F(n - 1) = 2 * F(n) + F(n - 1)
      Đến đây thì các bạn nhân ma trận là xong!

      • SBD12_LamLDK 9:37 a.m. 27 Tháng 6, 2024

        This comment is hidden due to too much negative feedback. Click here to view it.

        • SBD12_LamLDK 9:36 a.m. 27 Tháng 6, 2024

          This comment is hidden due to too much negative feedback. Click here to view it.

          • anhduc11092014 1:52 p.m. 13 Tháng 6, 2024

            lời giải của em bị sai ở đâu vậy:
            def fibo(n):
            if n == 1 or n == 0:
            return n
            else:
            return fibo(n - 1) + fibo(n - 2)

            n = int(input()) + 2
            tg = fibo(n)
            print(tg - 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

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