题解：P1962 斐波那契数列

· · 题解

题目传送门。\ 提交记录。

题目思路

运用矩阵快速幂实现。

首先推出递推，我们的目标如下：

\begin{bmatrix} F_{n-1} \\F_n \end{bmatrix}

先要写出状态转移方程，要从上一个状态转到本状态。接着，根据矩阵的特性，我们知道转移矩阵一定为二行二列。得：

\begin{bmatrix} F_{n-2} \\F_{n-1} \end{bmatrix} \begin{bmatrix} a & b \\ c & d \end{bmatrix}= \begin{bmatrix} F_{n-1} \\F_{n} \end{bmatrix}

然后，矩阵相乘，得：

aF_{n-2}+bF_{n-1}=F_{n-1} cF_{n-2}+dF_{n-1}=F_n

最后，得出：

\begin{bmatrix} a & b \\ c & d \end{bmatrix}= \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}

AC CODE:

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long a[5][5],c[5][5];
long long n;
long long res[5][5];
void mul(long long a[5][5],long long b[5][5],long long c[5][5]){
    memset(res,0,sizeof(res));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int p=1;p<=2;p++){
                res[i][j]=(res[i][j]+1ll*a[i][p]*b[p][j]%mod)%mod;
            }
        }
    }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            c[i][j]=res[i][j];
        }
    }
}
void q(long long a[5][5],long long b,long long c[5][5]){
    if(b==0){
        memset(c,0,sizeof(c));
        for(int i=1;i<=2;i++)
        c[i][i]=1;
        return ;
    }
    if(b%2==1){
        q(a,b-1,c);
        mul(c,a,c);
        return ;
    }
    q(a,b/2,c);
    mul(c,c,c);
    return ;
}
int main() {
    cin>>n;
    if(n<=2){
        cout<<1;
        return 0;
    }
    a[1][2]=a[2][1]=a[2][2]=1;
    q(a,n-1,c);
    cout<<(c[1][1]+c[2][1])%mod<<"\n";
    return 0;
}