hdu 1250 Hat's Fibonacci

点击此处即可传送hdu 1250

Problem Description

A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
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)
Your task is to take a number as input, and print that Fibonacci number.





Input

Each line will contain an integers. Process to end of file.





Output

For each case, output the result in a line.




Sample Input

100





Sample Output

4203968145672990846840663646


Note:
No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

解题思路：就是一个大数的高精度，但是一定别一个一个的感觉会超时，我没有试过，直接上代码吧，代码应该挺好懂的：

/*
2015 - 8 - 13
Author: ITAK
今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 10000;//大约是8000多，网上说的
const int M = 300; //每个元素可以存储8位数字，所以2005位可以用300个数组元素存储。
//如果用2005的话感觉会超时
int Feb[N][M];

void Solve()
{
    memset(Feb, 0, sizeof(Feb));
    Feb[1][1] = 1;
    Feb[2][1] = 1;
    Feb[3][1] = 1;
    Feb[4][1] = 1;
    for(int i=5; i<N; i++)
    {
        int k = 0;//计位的
        for(int j=1; j<M; j++)
        {
            k += Feb[i-1][j]+Feb[i-2][j]+Feb[i-3][j]+Feb[i-4][j];
            Feb[i][j] = k%100000000;
            k /= 100000000;
        }
    }

}
int main()
{
    int m;
    Solve();
    while(~scanf("%d",&m))
    {
        int i = M-1;
        while(!Feb[m][i])
            i--;
        printf("%d",Feb[m][i--]);
        while(i > 0)
        {
            printf("%08d",Feb[m][i]);
            i--;
        }
        puts("");
    }
    return 0;
}