Đ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
nhân ma trận tìm số fibo thứ n+3 rồi lấy kết quả -1
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\)
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!