hdu 1250 Hat's Fibonacci 高精度问题 预处理

原题链接 http://acm.hdu.edu.cn/showproblem.php?pid=1250

题目大意根据公式 F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)，输入一个数n，输出F(n)。F(n)可能有2005位数。

虽然做过一些大数的题，但这道题还是很怕TLE，这题用到大数相加，用数组的元素表示大数的各个数位的数字，（例如123，可以a[0]=3,a[1]=2,a[2]=1;）有个技巧是在网上学到的，每个数组元素存储八位数可以提高效率。先预处理，再输入数据。

代码和思路：

#include<stdio.h>
int a[10000][260]={0};   //每个元素可以存储8位数字，所以2005位可以用260个数组元素存储。（稍微取大一点）
int main()
{
	int i,j,n;
	a[1][0]=1;      //赋初值
	a[2][0]=1;
	a[3][0]=1;
	a[4][0]=1;
	for(i=5;i<10000;i++)
	{
		for(j=0;j<260;j++)
			a[i][j]+=a[i-1][j]+a[i-2][j]+a[i-3][j]+a[i-4][j];
		for(j=0;j<260;j++)                //每八位考虑进位。
			if(a[i][j]>100000000)
			{
				a[i][j+1]+=a[i][j]/100000000;
				a[i][j]=a[i][j]%100000000;
			}
	}
    while(scanf("%d",&n)!=EOF)
	{
		for(j=259;j>=0;j--)
			if(a[n][j]!=0) break;      //不输出高位的0
		printf("%d",a[n][j]);
		for(j=j-1;j>=0;j--)
			printf("%08d",a[n][j]);     //每个元素存储了八位数字，所以控制输出位数为8，左边补0
		printf("\n");
	}
	return 0;
}