题目描述

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

$$ F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right. $$

请你求出 $F_n \bmod 10^9 + 7$的值。

输入格式

一行一个正整数 n

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

5

输出 #1

5

输入 #2

10

输出 #2

55

说明/提示

【数据范围】
对于 60% 的数据，$1\le n \le 92$；
对于 100% 的数据，$1\le n < 2^{63}$。

题目分析

题意很简单求斐波那契数列的第$n$项，但是坑点在于n的范围特别大，最大能达到$2^{63}$ ，$O(n)$级别的递归会导致超时。

斐波那契数列的递归公式:$F_{n}=F_{n-1}+F_{n-2}$ 。我们以矩阵的角度来看待这个递推式。

$$ \begin{bmatrix} f_{n-2} & f_{n-1} \end{bmatrix} \times \begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n-2}+f_{n-1} \end{bmatrix}= \begin{bmatrix} f_{n-1} & f_n \end{bmatrix} $$

可发现每次矩阵乘一下$ \begin{bmatrix}
0 & 1\
1 & 1
\end{bmatrix} $ 即可实现一次递推。设

$$ A=\begin{bmatrix} 0 & 1\\ 1 & 1 \end{bmatrix} $$

那么，求第n项，即成为求 $\begin{bmatrix}
0 & 1\
\end{bmatrix}
\times A^n$ 对应的第一个值。问题就变成了解决求$A^n$ ，我们可以采用[**矩阵快速幂**](https://algorithmnote.cn/?p=51)的方式在$O(logn)$ 的时间复杂度内完成。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=5;
const int M=1e9+7;
struct node{
    ll a[N][N];
    int row,col;
};
node I;//单位矩阵

node matrixMins(node a,node b){//矩阵乘法
    node c={0};//答案矩阵
    c.row=a.row;
    c.col=b.col;
    int n=c.row,p=c.col,m=a.col;
    //计算矩阵乘法
    for(int i=1;i<=n;i++){
        for(int j=1;j<=p;j++){
            for(int k=1;k<=m;k++){
                c.a[i][j]+=a.a[i][k]*b.a[k][j]%M;
                c.a[i][j]%=M;
            }
        }
    }
    return c;
}
node matrixPow(node a,ll k){//矩阵的幂次方
    if(k==0){// 0次方
        return I;//矩阵的0次方是单位矩阵
    }
    node t=matrixPow(a,k/2);//求 a^{n/2} 次方
    if(k&1){//判断k是否是奇数
        return matrixMins(matrixMins(t,t),a);
    }else{//k是偶数
        return matrixMins(t,t);
    }
}
int main(){
    node a={0};
    ll n;
    cin>>n;
    //处理斐波那契数列 递推矩阵
    a.col=a.row=2;
    a.a[1][1]=0;
    a.a[1][2]=a.a[2][1]=a.a[2][2]=1;
    //处理 单位矩阵
    I.col=I.row=2;
    I.a[1][1]=I.a[2][2]=1;
    I.a[1][2]=I.a[2][1]=0;
    //处理斐波那契数列初始值 [0 1]
    node tt={0};
    tt.row=1;tt.col=2;
    tt.a[1][1]=0;
    tt.a[1][2]=1;
    
    node tmp=matrixPow(a,n);//计算A^n
    node ans=matrixMins(tt,tmp);
    cout<<ans.a[1][1];
    return 0;
}