递归版本

#include <bits/stdc++.h>
using namespace std;
int book[1000000+5]; //记忆化，book[i] 记住斐波那契数列第i项 
//返回数列第 x 项
int f(int x)
{
	if(book[x]!=-1)
		return book[x];//之前算过就直接返回 
    if (x == 1)
        return 1;
    if (x == 2)
        return 1;
    book[x] = (f(x - 1) + f(x - 2))%1000;//算完后先别返回，先记下来 
    return book[x];
}
int main()
{
	//一开始把本子清空 
	for(int i=1;i<=1000000;i++)
		book[i] = -1; 
    int n;
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
	    cin >> n;
    	cout << f(n) % 1000 << "\n";
	}
	return 0;
}

一个典型的斐波那契数列。

重点是数据量大需要注意取模。

使用一个数组做一个记忆化，避免重复操作超时。

其实这也是一种动态规划

其他的可以看代码。

#include<bits/stdc++.h>
using namespace std;
int book[1000010]={0};
int n;
int main()
{
	for(int i=0;i<=1000005;i++)
		book[i]=-1;
//初始化；注意一定要为不可能的数字，如果初值为0的话会出问题的！
	book[1]=1,book[2]=1;
//1、2两个数字均为1
	for(int i=3;i<=1000000;i++)
		if(book[i]==-1)
			book[i]=(book[i-1]+book[i-2])%1000;
//如果第i个数字不为-1，即没有使用过（其实不需要也可以不是吗），进行运算
//从1-1000000次循环确实有点暴力了
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		cout<<book[x]<<'\n';
//直接输出数组相应位数
	}
	return 0;
}