#include<bits/stdc++.h>
using namespace std;
long n;
long a[1000005];
long long x[10000005];
int main(){
	cin>>n;
	x[0]=1;
	x[1]=1;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=2;i<1000005;i++){
		x[i]=(x[i-1]+x[i-2])%1000;
	}
	for(int i=0;i<n;i++){
		cout<<x[a[i]-1]<<endl;
	}
	return 0;
}

数组定义一定要大

递归可以，但要用记忆化

#include <bits/stdc++.h>
using namespace std;
int a[1000005];
int fibonacci(long long n){
	if (a[n])	return a[n];	// 有记忆就调用
	if(n == 1 || n == 2){
		return a[n] = 1;	// 存记忆
	}else{
		return a[n] = (fibonacci(n - 1) % 1000) + (fibonacci(n - 2) % 1000);	// 存记忆
	}
}
int main(int argc, char **argv){
	int n;long long x;
	cin >> n;
	for (int i = 0;i < n;i++){
		cin >> x;
		printf("%d\n",fibonacci(x) % 1000);
	}
	return 0;
}

有种东西叫做记忆化递归

#include<iostream>
using namespace std;
const int N=1e6;
long long sa[N];//记忆数组
long long f(long long x)
{
	if(sa[x])//如出现过就返回之前的值
	{
		return sa[x];
	}
	if(x<=2)//边界
	{
		sa[x]=1;
		return sa[x];
	}
	else
	{
		sa[x]=f(x-1)%1000+f(x-2)%1000;
		return sa[x];//递归与同余
	}
}
int main()
{
	int n;
	cin>>n;//输入
	while(n--)
	{
		int x;
		cin>>x;//输入
		cout<<f(x)%1000<<endl;//输出
	}
	return 0;//完结散花
}

程序填空('-' )

#include<cstdio>
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std ;
const int MAX = (1);
long long a[MAX];
long long akm(int n)
{
	if(a[n])
	{
		return a[n];
	}
	if(n==1||n==2)
	{
		a[n]=1;
		return a[n]; 
	}
	else 
	{
		a[n] = (2)%1000;
		return (3);
	}
}
int main()
{
	int n,i=0;
	cin>>n;
	while(4)
	{
		cin>>i;
		cout<<akm(5)<<endl;
	}
	
	return 0;
}

#include<cstdio>
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std ;
const int MAX = 100000;//要把数组开大亿亿点点
long long a[MAX];
long long akm(int n)
{
	if(a[n])
	{
		return a[n];
	}
	if(n==1||n==2)
	{
		a[n]=1;
		return a[n]; 
	}
	else 
	{
		a[n] = (akm(n-1)%1000+akm(n-2)%1000)%1000;//取模！取模！取模！注意取模啊啊啊啊啊啊啊啊啊！
		return a[n];
	}
}
int main()
{
	int n,i=0;
	cin>>n;
	while(n--)
	{
		cin>>i;
		cout<<akm(i)%1000<<endl;//为了保险还是要取模
	}
	
	return 0;
}

不要抄哦（^-^ )

using namespace std;
int s(int n)
{
int s1=0,s2=1;;
if(n==1)return 1;
if(n==2)return 1;
int temp=0;
if(n<0)return 0;
else temp=(s(n-1)+s(n-2));
}
int main()
{
int n;
cin>>n;
int a;
for(int i=1;i<=n;i++)
{
cin>>a;
cout<<s(a)%1000;
	}
}