P1962 斐波那契数列

题目背景

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

• 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
        
         #define mod 1000000007LLusing namespace std;struct Node{    long long m[3][3];    Node(){memset(m,0,sizeof(m));}    }ans,mb;Node operator*(Node a,Node b)//矩阵乘法 {    Node c;    for(int i=1;i<=2;i++)      for(int j=1;j<=2;j++)        for(int k=1;k<=2;k++)          c.m[i][j]=(c.m[i][j]%mod+a.m[i][k]*b.m[k][j]%mod)%mod;    return c;}long long n;int main(){    cin>>n;    mb.m[1][1]=mb.m[1][2]=mb.m[2][1]=1;    ans.m[1][1]=ans.m[2][1]=1;    while(n>0)    {        if(n&1) ans=ans*mb;        mb=mb*mb;n>>=1;    }    cout<