题目背景

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

• 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)范围内。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define ll long long 6 using namespace std; 7 const ll Mod=1000000007; 8 ll n; 9 struct matrix{ll m[5][5];}a;10 matrix multiply(matrix a,matrix b){11     matrix t;12     for(int i=1;i<=2;i++)13         for(int j=1;j<=2;j++){14             t.m[i][j]=0;15             for(int k=1;k<=2;k++)16                 t.m[i][j]=(t.m[i][j]+a.m[i][k]*b.m[k][j])%Mod;17         }18     return t;19 }20 matrix fast(matrix a,ll p){21     matrix ans=a;p--;22     while(p>0){23         if(p&1) ans=multiply(ans,a);24         a=multiply(a,a);25         p>>=1;26     }27     return ans;28 }29 int main(){30     a.m[1][2]=a.m[2][1]=a.m[2][2]=1;31     scanf("%lld",&n);32     matrix tmp=fast(a,n);33     printf("%lld",tmp.m[1][2]);34     return 0;35 }