Fibonacci_牛客博客

菲波那契数列是指这样的数列: 数列的第一个是0和第二个数是1，接下来每个数都等于前面2个数之和。给出一个正整数a，要求菲波那契数列中第a个数的后四位是多少。Input多组数据 -1结束范围1~10^9Output第x项的后4位Sample Input

Sample Output

0
34
626

	6875



	



	



	



	



	代码：



	#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;

const long long mod=10000;
long long f=2;
long long n;

struct node
{     long long matrix[5][5];
};

node mul(node a,node b)
{     node ans;     memset(ans.matrix,0,sizeof(ans.matrix));     for(long long i=1;i<=f;i++)     {         for(long long j=1;j<=f;j++)         {             for(long long k=1;k<=f;k++)             {                 ans.matrix[i][j]=(ans.matrix[i][j]+a.matrix[i][k]*b.matrix[k][j]%mod+mod)%mod;             }         }     }     return ans;
}

node ksm(node a,long long b)
{     node res;     memset(res.matrix,0,sizeof(res.matrix));     for(long long i=1;i<=f;i++)         res.matrix[i][i]=1;     while(b)     {         if(b&1) res=mul(res,a);         b>>=1;         a=mul(a,a);     }     return res;
}

int main()
{     while(cin>>n)     {                  if(n==-1) return 0;         if(n==0)         {             cout<<"0"<<endl;             continue;                      }          if(n==1||n==2)          {             cout<<"1"<<endl;continue;         }         else         {             node a,b;             a.matrix[1][1]=1;a.matrix[1][2]=0;             a.matrix[2][1]=1;a.matrix[2][2]=0;             b.matrix[1][1]=1;b.matrix[1][2]=1;             b.matrix[2][1]=1;b.matrix[2][2]=0;             node ans=ksm(b,n-2);             ans=mul(ans,a);             cout<<ans.matrix[1][1]<<endl;         }     }     return 0;
}