【ETOJ P1046】斐波那契数列 题解（数学+动态规划）
题目描述
给定一个整数 T T T，表示样例数。
对于每个样例，给定一个整数 n n n，求斐波那契数列的第 n n n 项。
斐波那契数列定义为 f ( 1 ) = f ( 2 ) = 1 f(1) = f(2) = 1 f(1)=f(2)=1， f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n−1) + f(n−2) f(n)=f(n−1)+f(n−2)。
结果对 1 0 9 + 7 10^9 + 7 109+7 取模。
输入格式
第一行一个整数 T T T。（ 1 ≤ T ≤ 100 1 ≤ T ≤ 100 1≤T≤100）
对于每个样例，一个整数 n n n。（ 1 ≤ n ≤ 100 1 ≤ n ≤ 100 1≤n≤100）
输出格式
对于每个样例，输出一个整数表示答案。
样例输入1
2
3
5
样例输出1
2
5
思路
斐波那契数列是一个非常经典的递归序列，其定义为：F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2) (n>=2)。
首先定义了一个数组f，用于存储斐波那契数列的值。然后先将斐波那契数列的前两项设为1，这是斐波那契数列的定义。接下来，通过一个循环，计算出斐波那契数列的前100项。在计算每一项的时候，都用前两项的和对一个大数（1e9+7）取模，防止数值过大导致的溢出。
在计算完斐波那契数列的前100项之后，程序进入一个循环，每次从输入中读取一个数n，然后输出斐波那契数列的第n项。这个循环会一直进行，直到没有更多的输入。
AC代码
#include <iostream>
#define ll long long
#define AUTHOR "HEX9CF"
using namespace std;
const int N = 1e2 + 7;
const int MOD = 1e9 + 7;
ll f[N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
f[1] = f[2] = 1;
for (int i = 3; i <= 100; i++) {
f[i] = (f[i - 1] + f[i - 2]) % MOD;
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << f[n] << endl;
}
return 0;
}