Cho dãy số Fibonacci được xác định như sau: F1=F2=1,Fn=Fn−1+Fn−2,∀n≥3. Một số số hạng ban đầu của dãy như sau: 1,1,2,3,5,8,13,21,34... Yêu cầu: Tính số Fibonacci thứ n, kết quả có thể rất lớn nên ta phải chia lấy dư cho 1000000007 Dữ liệu: Số nguyên dương n (0<n<106) Kết quả: Fn%1000000007 Ví dụ input 3 output 2 c++ ná
1 câu trả lời
#include <iostream>
using namespace std;
const int Mod = int(1e9) + 7;
int f[1000000];
int main() {
int n; cin >> n;
f[1] = f[2] = 1;
for (int i = 3; i <= n; ++i) {
f[i] = (f[i - 1] + f[i - 2]) % Mod;
}
cout << f[n];
}
Câu hỏi trong lớp
Xem thêm
