HDU 大数加 - 1250 Hat's Fibonacci

一个新的斐波那契数列，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)

没什么可说的，大数加上，注意为了节省空间，我们使用滚动数组，一开始我还以为能一开始算出所有可能来节省时间，后来发现空间真是hold不住啊。。

#include<stdio.h>
#include<string.h>
#define MAX 2010
int a[6][MAX];

void add(int x,int y){
	int xlen= a[x][2009];
	int len = a[y][2009];
	int tlen=xlen;
	int i,j,temp;
	for(i=0;i<len;i++){
		a[x][i] += a[y][i];
		if(a[x][i]>9){
			if(i==xlen-1){
				tlen=len+1;
			}
			a[x][i]-=10;
			a[x][i+1]+=1;
		}
	}
	a[x][2009]=tlen;
}
int main(){
	int i,n;
	while(scanf("%d",&n)!=EOF){
		memset(a,sizeof(a));
		for(i=0;i<4;i++){
			a[i][0]=1;
			a[i][2009]=1;
		}
		for(i=4;i<=n;i++){
			memcpy(a[i%5],a[(i-1)%5],MAX*sizeof(int));
			add(i%5,(i-2)%5);add(i%5,(i-3)%5);add(i%5,(i-4)%5);
		}
		for(i=a[(n-1)%5][2009]-1;i>=0;i--){
			printf("%d",a[(n-1)%5][i]);
		}
		printf("n");
	}
}