/*

中文题意：

中文翻译：

题目大意：求1000以内的菲波数。

解题思路：用大数来计算。用二维数组来存数。

难点具体解释：用二维数组存数，開始的一维存的是1000个Pi，后面那一维是用来存数字的。

关键点：大数高精度算法

解题人：lingnichong

解题时间：2014/7/31    20:42        改动日期：2014/08/01    00:31

解题感受：

*/

大菲波数

5

1

2

3

4

5

1

1

2

3

5

#include<stdio.h>

#include<string.h>

#define Pi 1010

#define MAXN 2500

int f[Pi][MAXN];

int main()

{

	int i,j,k;

	memset(f,0,sizeof(f));

	f[1][0]=f[2][0]=1;

	for(i=3;i<Pi;i++)

	{

		for(j=MAXN-1;j>=0;j--)

		if(f[i-1][j]!=0)  break;//找到上一个数右边第一个不是0的数的下标

		for(k=0;k<=j;k++)

		{

			f[i][k]+=(f[i-1][k]+f[i-2][k]);//保留进位所得数，所以是+=

			if(f[i][k]>=10)

			{

				f[i][k]-=10;

				f[i][k+1]+=1;

			}

		}

	}

	int T,n;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		for(i=MAXN-1;(i>=0)&&(f[n][i]==0);i--);

		for(;i>=0;i--)

		printf("%d",f[n][i]);

		printf("\n");

	}

	return 0;

} 

/*

1000的斐波那契数

22

1000

43466557686937456435688527675040625802564660517371780402481729089536555417949051

89040387984007925516929592259308032263477520968962323987332247116164299644090653

3187938298969649928516003704476137795166849228875

999

26863810024485359386146727202142923967616609318986952340123175997617981700247881

68933836965448335656419182785616144335631297667364221035032463485041037768036733

4151172899169723197082763985615764450078474174626

998

16602747662452097049541800472897701834948051198384828062358553091918573717701170

20106551018559589860510409473691887927846223301598102952299783631123261876053919

9036765399799926731433239718860373345088375054249

*/