题解：P1962 斐波那契数列

Python_enjoy · 2026-01-26 13:39:09 · 题解

题目大意

求斐波那契额数列的第 n 项。

做法

我们看到数据范围就会知道：不可以用递推。

此时我们可以使用矩阵来加速！

想到下面这个式子：

这个矩阵 A 是多少行多少列的呢？抽象一下式子：

这下很容易得出，x=2 且 y=2。那么再根据 F_n=F_{n-1}+F_{n-2}，可以得出：

朋友，有没有考虑 n\leq2 的时候？设 \begin{bmatrix} F_2 \\ F_1 \end{bmatrix} = B，易得 B=\begin{bmatrix} 1 \\ 1 \end{bmatrix}，进一步得到结论：

直接暴力算这个 \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{n-2} 肯定会 TLE，所以可以使用矩阵快速幂加速。

AC 代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100+5;
const int p=1e9+7;
int n,k;
struct det{
    int a[N][N];
    det(){
        memset(a,0,sizeof a);
    }
    friend det operator * (det a,det b)
    {
        det c;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                for(int k=1; k<=n; k++)
                {
                    c.a[i][j]=0;
                }
            }
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                for(int k=1; k<=n; k++)
                {
                    c.a[i][j]+=a.a[i][k]*b.a[k][j];
                    c.a[i][j]%=p;
                }
            }
        }
        return c;
    }

}a,b,c,d,e;

det qpow(det a,int b)
{
    det result;
    for(int i=1; i<=n; i++)
    {
        result.a[i][i]=1;
    }
    while(b>0)
    {
        if(b&1)
        {
            result=result*a;
        }
        a=a*a;
        b>>=1;
    }
    return result;
}
int m;
signed main()
{
    cin>>m;
    n=2;
    a.a[1][1]=a.a[1][2]=a.a[2][1]=1;
    a.a[2][2]=0;
    c=qpow(a,m-2);
    cout<<(c.a[1][1]+c.a[1][2])%p;
    return 0;
}