Hat's?Fibonacci

Time?Limit:?2000/1000?MS?(Java/Others)????Memory?Limit:?65536/32768?K?(Java/Others)
Total?Submission(s):?9518????Accepted?Submission(s):?3135

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.

?

#include<stdio.h>

#include<string.h>

using?namespace?std;

struct?big

{

????int?a[500];

????int?t;

}f[7050];

//设置数组简直口怕.

int?main()

{

????int?i,j,tmp;//tmp用来表示余数和进位数.

????for(i=0;i<7050;i++)

????{

????????f[i].t=1;

????}

?????f[1].a[0]=f[2].a[0]=f[3].a[0]=f[4].a[0]=1;

?????/////////////初始化完毕.

?????for(i=5;i<7050;i++)

?????{

?????????f[i].t=f[i-1].t;

?????????for(tmp=j=0;j<f[i].t;j++)

?????????{

??????????????f[i].a[j]=(f[i-1].a[j]+f[i-2].a[j]+f[i-3].a[j]+f[i-4].a[j]+tmp)%1000000;??//取6位数字

??????????????tmp=(f[i-1].a[j]+f[i-2].a[j]+f[i-3].a[j]+f[i-4].a[j]+tmp)/1000000;??//记录进位

?????????}

?????????if(tmp!=0)

?????????{

?????????????f[i].a[f[i].t]=tmp;

?????????????f[i].t++;

?????????}

?????}

while?(scanf("%d",&i)?==?1)

?{

??j=f[i].t-1;

??printf("%d",f[i].a[j]);//打印的时候防止输入1的时候输出000001

??for(j--;j>=0;j--)

??{

???printf("%06d",f[i].a[j]);??//打印时用0补齐位数

??}

??printf("n");

?}

?return?0;

}