Hat's Fibonacci

  
  

   
   100
  
  

  
  

   
   4203968145672990846840663646


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

题意：首先，该题给出了一个类似于斐波那契数列的数列的前4项以及它的递推式，要求我们求出第n项(关于n的范围，题目只告诉我们任何一项的值位数都在2005位以内)

解题思路：因为递推式也已经知道了，此题无非就是一道大数加法的题目，解决方案大体分为两种

①对于给出的n，每次都从第5项开始重新计算，这样做节省了空间，但是时间复杂度就比较高了，几百MS应该是要的吧

②另一种则无非是空间换时间，在预处理阶段就先提前算好所有项的值

第②方法15MS就差不多了，但是我们可以来算算，每一项至少要留出2005的空间，而根据测试 到 7060项 的时候长度为 2012位，那就至少得开一个7061*2012的字符数组

orz

难逃MLE的命运

然而，这里有一种甚妙的解决方法：

我们都清楚一点，平时模拟大数加法的时候，我们都是数组的1个单元表示数的一位，比如说1314，我们或许就开了s[4]的数组，每一下标地址存储1314的一位，其实，我们完全可以只开s[1]的数组，存取1314的四位，这样就节省了3/4的空间，当然，你也可以存5位或者6位等等

以下给出该数列一些项的值以供参考：

#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 7061;
const int inf = 2147483647;
const int mod = 2009;
int s[N][504],l[N];
int main()
{
    int n,i,j;
    s[1][0]=s[2][0]=s[3][0]=s[4][0]=1;
    l[1]=l[2]=l[3]=l[4]=1;
    for(i=5;i<N;i++)
    {
        for(j=0;j<l[i-1];j++)
        {
            s[i][j]+=s[i-1][j]+s[i-2][j]+s[i-3][j]+s[i-4][j];
            s[i][j+1]+=s[i][j]/10000;
            s[i][j]%=10000;
        }
        while(s[i][j]>0)
        {
            s[i][j+1]+=s[i][j]/10000;
            s[i][j]%=10000;j++;
        }
        l[i]=j;
    }
    while(~scanf("%d",&n))
    {
        printf("%d",s[n][l[n]-1]);
        for(i=l[n]-2;i>=0;i--)
            printf("%4.4d",s[n][i]);
        puts("");
    }
    return 0;
}