题目描述定义一个数列fi = fi-1+fi-2 f0 = 0 f1 = 1求fn mod 1e9+7输入数据一个正整数nn=1e5输出数据fn mod 1e9+7c++保证时间在1000ms之间

解题思路 根据题目给出的数列定义，可以使用递归或循环来计算f(n)。但由于递归的时间复杂度较高，容易导致超时，因此选择使用循环来计算。

具体算法如下：

1. 定义两个变量a和b，分别表示f(i-2)和f(i-1)的值，初始值分别为0和1。
2. 使用循环从2开始遍历到n，每次更新a和b的值为b和a+b的和，即a = b, b = a+b。
3. 循环结束后，返回b mod (1e9+7)作为结果。

时间复杂度分析 由于只需进行一次循环，每次循环的操作只有简单的赋值和加法运算，时间复杂度为O(n)，在n <= 1e5的情况下，能够在1000ms内完成计算。

C++代码实现如下：

#include using namespace std;

int main() { int n; cin >> n;

int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
    int temp = (a + b) % (int)(1e9+7);
    a = b;
    b = temp;
}

cout << b << endl;

return 0;