题目背景

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

• 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 的值

（n<=1e18）

思路：

我们已经知道递推公式了，但有个问题，就是n太大

怎么办呢？

我前面写过一个，大家应该看过。

那么，这里我们就要用矩阵快速幂来优化

我们将原数列抽象为这样的一个矩阵：

{  fn  , 0 }

{fn-1，0}

那么，我们将原矩阵乘上这样的一个矩阵：

{1,1}

{1,0}

就变成了这样：

{fn+fn-1，0}

{    fn    ，0}

整个矩阵向着斐波那契的下一项方向移动

OK，现在我们就不用O（n）地移动了，O（logn）即可

（关于矩阵快速幂部分，请参见我以前的一篇博客（上面有链接））

代码：

#include
     
      #include
      
       #include
       
        #define rii register int i#define rij register int j#define rik register int k#define mod 1000000007using namespace std;struct j{    long long jz[5][5];}x,y,z,an;long long n;long long ys[5];inline j cheng(j l,j r){    j ltt;    long long ans=0;    ltt.jz[1][1]=0;    ltt.jz[1][2]=0;    ltt.jz[2][1]=0;    ltt.jz[2][2]=0;    for(rii=1;i<=2;i++)    {        for(rij=1;j<=2;j++)        {            ans=0;            for(rik=1;k<=2;k++)            {                ans+=(l.jz[i][k]*r.jz[k][j]);                ans%=mod;            }            ltt.jz[i][j]=ans;        }    }    return ltt;}j pw(j k,long long c){    if(c==1)    {        y=cheng(y,k);        return y;    }    if(c%2==0)    {        k=cheng(k,k);        pw(k,c/2);    }    else    {        c--;        y=cheng(k,y);         pw(k,c);    }}int main(){    x.jz[1][1]=1;    x.jz[1][2]=1;    x.jz[2][1]=1;    y.jz[1][1]=1;    y.jz[2][2]=1;    an.jz[1][1]=1;    an.jz[2][1]=1;    scanf("%lld",&n);    if(n==1)    {        cout<<1;        return 0;    }    if(n==2)    {        cout<<"1";        return 0;    }    pw(x,n-2);    an=cheng(y,an);    cout<