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
7Note
- \(S = 1+1+2+3\)
Test 1
Input
5 Output
20Note
- \(S = 1+1+2+3+5+8\)
Nguồn: CĐ DHBB
Bình luận
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!
5 bình luận nữa