hdu 1250 Hat's Fibonacci

hdu ? 1250 ? Hat's Fibonacci ? ? ? ? ? ? ? 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1250

题目大意：一个斐波纳契小变形，公式已给出。

题目分析：大数无坑，第一维N代表第几个此数列中的数，第二位中首位0存的是万进制下有多少位，后面就是万进制从低到高存下的数了。

code:

#include<stdio.h>
#define N 7500
//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)
int i,j,k,a[N][600];
int add(int n)
{
    for(j=1;j<=a[n-1][0];j++)
    {
        for(k=1;k<5;k++)
        {
            a[n][j]+=a[n-k][j];
        }
        a[n][j+1]+=a[n][j]/10000;
        a[n][j]%=10000;
    }
    if(a[n][j])return j;
    else return j-1;
}
void init()
{
    for(i=1;i<5;i++)
    {
        a[i][0]=a[i][1]=1;
    }
    for(i=5;i<N;i++)
    {
        a[i][0]=add(i);//存位数
    }
}
int main()
{
    int n,q;
    init();
    while(~scanf("%d",&n))
    {
        printf("%d",a[n][q=a[n][0]]);//第一位还是要正常输出的
        while(q>1)printf("%04d",a[n][--q]);//%04可补0
        putchar('n');
    }
    return 0;
}

PS：做这个题还是有一定收获的，复习了一下大数，格式输出中的“%04”，还有。一开始我是用short定义数组，想节省一点内存，结果自己整的样例不过，出现了负数，一想short只能存32768，万进制下如果有四个9000，就必然超了。写到这里，突然想到unsigned short，就改交了一遍，水过……