题目背景

大家都知道，斐波那契数列是满足如下性质的一个数列：

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

请你求出 f(n) mod 1000000007 的值。

输入输出格式

输入格式：

 

·第 1 行：一个整数 n

 

输出格式：

 

第 1 行： f(n) mod 1000000007 的值

 

输入输出样例

输入样例#1：

5

输出样例#1：

5

输入样例#2：

10

输出样例#2：

55

说明

对于 60% 的数据： n ≤ 92

对于 100% 的数据： n在long long(INT64)范围内。

 

题解：

矩阵乘法裸题，可以自行学习。然后就不难了。

 

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define mod 1000000007#define ll long longusing namespace std;struct zhen{    ll a[2][2];};zhen jvchen(zhen x,zhen y){    zhen hhh;memset(hhh.a,0,sizeof(hhh.a));    for(int i=0;i<=1;i++)        for(int j=0;j<=1;j++)            for(int k=0;k<=1;k++){                hhh.a[i][j]+=x.a[i][k]*y.a[k][j];                hhh.a[i][j]%=mod;            }    return hhh;}zhen query(zhen hh,ll nn){    zhen ans;    ans.a[0][0]=0;    ans.a[0][1]=1;    ans.a[1][0]=0;    ans.a[1][1]=0;    while(nn){        if(nn&1) ans=jvchen(ans,hh);        hh=jvchen(hh,hh);        nn>>=1;    }    return ans;}int main(){    ll n;cin>>n;    zhen hh;    hh.a[0][0]=0;    hh.a[0][1]=1;    hh.a[1][0]=1;    hh.a[1][1]=1;    zhen ans=query(hh,n-1);    printf("%lld",ans.a[0][1]);}