题解：P1962 斐波那契数列

a202401006 · 2026-01-25 17:01:45 · 题解

题目传送门

解析

题目大意

求斐波那契数列的 F_n \bmod 10^9+7 的值。其中，斐波那契 F_n 的规律如下。

考察知识

本题考查矩阵乘法、快速幂、数学。

思路

看一眼题目，发现底部有这么一句话；对于 100\% 的数据，1\le n < 2^{63}。一看便知道，包会超时限。

题目的标签提醒了一下：数学、递推、矩阵运算和矩阵乘法。

的确，这一题要用矩阵快速幂去做。

:::info[矩阵快速幂] 首先了解一下什么是矩阵快速幂。有需要的可以前往矩阵快速幂的模板题进行学习，这里简单地讲一下。

矩阵快速幂指的就是一个矩阵的若干次方的结果，矩阵怎么进行幂运算？很简单，也就是若干个原来的矩阵相乘。举个例子：假设有一个矩阵 A，那么 A 的 4 次方就是 A^4=A\times A\times A\times A。那矩阵怎么进行乘法运算？给出一条矩阵乘法计算 A\times B=C 的核心公式：C_{i,j} = \sum_{k=1}^MA_{i,k}B_{k,j}

没看懂？文字解释就是：结果矩阵 C 中第 i 行第 j 列的数，等于矩阵 A 的第 i 行和 B 的第 j 列对应位置相乘后，再全部加起来。

至于快速幂，这里就不讲了，如有需要可以前往快速幂的模板题。 :::

相信大家都知道斐波那契数列，题目里面也有。这一题虽然使用矩阵快速幂进行优化，但是不变的仍然是那条斐波那契数列的公式 F_n=F_{n-1}+F_{n-2}(n\ge 3)。设 F(n) 表示一个 1 \times 2 的矩阵 \left[ \begin{array}{ccc}F_n & F_{n-1} \end{array}\right]，则 F_{n-1} 表示 \left[ \begin{array}{ccc}F_{n-1} & F_{n-2} \end{array}\right]。

要想让 F(n-1) 推出 F(n)，那么必须得要乘上另外一个矩阵 C。根据矩阵乘法的公式，可以得到：C 的第一列的两个数都是 1，第二行的两个数分别是 1 和 0。

也就是说，C=\left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right] 且 F(n-1)\times C=\left[ \begin{array}{ccc}F_{n-1} & F_{n-2} \end{array}\right]\times \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]=F(n) 其中 n\ge 3。

由于 F_1=1 且 F_2=1，所以不妨设一个矩阵 A=\left[\begin{array}{ccc}F_2 & F_1\end{array}\right] = \left[\begin{array}{ccc}1 & 1\end{array}\right]，易得 n\ge 3 时，F(n)=A\times C^{n-2}=\left[\begin{array}{ccc}1 & 1\end{array}\right] \times \left[\begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array}\right]^{n-2}。

代码

//998244353
#include<bits/stdc++.h>
#define int long long
#define itn int
using namespace std;
const int MOD=1e9+7;
int n;
struct node
{
    int matrix[5][5];
    node(){memset(matrix,0,sizeof(matrix));};
}A,C;

inline node operator*(node x,node y)
{
    node t;
    for(int i=1;i<=2;i++)
    {
        for(itn j=1;j<=2;j++)
        {
            for(int k=1;k<=2;k++)
            {
                t.matrix[i][j]=(t.matrix[i][j]+x.matrix[i][k]*y.matrix[k][j])%MOD;
            }
        }
    }
    return t;
}

inline void quickpow(int k)
{
    while(k)
    {
        if(k%2)
        {
            A=A*C;//注意千万不要弄反了，必须是A*C而不是C*A，否则就会发现，原本一直都应该只有一行的矩阵A变成了两行
        }
        k/=2;
        C=C*C;
    }
}

signed main()
{
    cin>>n;
    if(n<=2)
    {
        cout<<1;
        return 0;
    }
    A.matrix[1][1]=1;
    A.matrix[1][2]=1;
    C.matrix[1][1]=1;
    C.matrix[1][2]=1;
    C.matrix[2][1]=1;
    C.matrix[2][2]=0;
    quickpow(n-2);
    cout<<A.matrix[1][1]%MOD;
}