递推基础题。对于洛谷的测试，此方法可以AC。acwing不行。

此问题就是个斐波那契数列f(x)=f(x-1)+f(x-2)。但由于数据过大，只能再用高精配合

思路：

1.定义三个数组，分别代表f(x)、f(x-1)、f(x-2)。

2.一个递推函数

3.一个高精度函数

4.一个复制函数，在x值变化时改变三个数组的对应值

首先是主函数

代码：

int main()
{
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	a[0]=1;
	b[0]=2;
	int n;
	cin>>n;
	if(n==1)
	{
		cout<<1;
		return 0;
	}
	if(n==2)
	{
		cout<<2;
		return 0;
	}//这两种情况直接输出 
	for(int i=3;i<=n;i++)
	{
		louti();
		gaojing();
		fuzhi();
	}
	for(int i=cnt;i>=0;i--)
	{
		if(i==cnt&&c[i]==0)
		{
			continue;
		}
		cout<<c[i];
	}
}

  没什么好说的

  函数2（递推）：

void louti()
{
	memset(c,0,sizeof(c));
	for(int i=0;i<cnt;i++)
	{
		c[i]+=a[i];
		c[i]+=b[i];
	}
}

 注意，此函数中必须有

memset(c,0,sizeof(c));

  因为c（答案数组）的值并非一个累计的值，在复制函数后，c所代表的值是一个空域，需要加进去。

函数3（高精）：

void gaojing()
{
	int k;
	for(int i=0;i<cnt;i++)
	{
		k=c[i];
		if(i==cnt-1&&c[i]>=10)
		{
			cnt++;
		}
		if(c[i]>=10)
		{
			c[i+1]+=k/10;
			c[i]%=10;
		}
		
	}
}

只需要做针对c的函数，原因下讲。

函数4（复制）：

void fuzhi()
{
	for(int i=0;i<cnt;i++)
	{
		a[i]=b[i];
		b[i]=c[i];
	}
}

 当c数组已经排列好后，a、b数组的值的来源便是c数组，所以就不用再针对a、b再次高精度运算。

总代码如下:

#include<bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005],c[1000005]/*答案数组*/;
int cnt=1;//计数 
void fuzhi()
{
	for(int i=0;i<cnt;i++)
	{
		a[i]=b[i];
		b[i]=c[i];
	}
}
void gaojing()
{
	int k;
	for(int i=0;i<cnt;i++)
	{
		k=c[i];
		if(i==cnt-1&&c[i]>=10)
		{
			cnt++;
		}
		if(c[i]>=10)
		{
			c[i+1]+=k/10;
			c[i]%=10;
		}
		
	}
}
void louti()
{
	memset(c,0,sizeof(c));
	for(int i=0;i<cnt;i++)
	{
		c[i]+=a[i];
		c[i]+=b[i];
	}
}
int main()
{
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	a[0]=1;
	b[0]=2;
	int n;
	cin>>n;
	if(n==1)
	{
		cout<<1;
		return 0;
	}
	if(n==2)
	{
		cout<<2;
		return 0;
	}//这两种情况直接输出 
	for(int i=3;i<=n;i++)
	{
		louti();
		gaojing();
		fuzhi();
	}
	for(int i=cnt;i>=0;i--)
	{
		if(i==cnt&&c[i]==0)
		{
			continue;
		}//没什么用的小代码。 
		cout<<c[i];
	}
}