当前位置：首页 > news >正文

斐波那契数列【牛客tracker 每日一题】

news 2026/5/11 22:21:03

斐波那契数列

时间限制：1秒空间限制：256M

知识点：
递归
基础数学

网页链接

示例1

输入：

输出：

解题思路

本题采用矩阵快速幂高效计算斐波那契数列第k kk项，核心是将斐波那契递推式转化为矩阵幂运算：斐波那契递推式F i = F i − 1 + F i − 2 F_i=F_{i-1}+F_{i-2}Fi=Fi−1+Fi−2可表示为矩阵乘法[ F i F i − 1 ] = [ 1 1 1 0 ] i − 2 [ F 2 F 1 ] \begin{bmatrix}F_i\\F_{i-1}\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^{i-2} \begin{bmatrix}F_2\\F_1\end{bmatrix}[FiFi−1]=[1110]i−2[F2F1]；先定义矩阵乘法和快速幂函数，初始化变换矩阵[ 1 1 1 0 ] \begin{bmatrix}1&1\\1&0\end{bmatrix}[1110]，对其进行( k − 2 ) (k-2)(k−2)次快速幂运算；最终通过矩阵结果计算F k = ( t m p [ 0 ] [ 1 ] + t m p [ 1 ] [ 1 ] ) m o d 1 e 9 + 7 F_k=(tmp[0][1]+tmp[1][1])\mod 1e9+7Fk=(tmp[0][1]+tmp[1][1])mod1e9+7。该方法时间复杂度为O ( log ⁡ k ) O(\log k)O(logk)，远优于递推的O ( k ) O(k)O(k)，适配k ≤ 10 6 k≤10^6k≤106的规模，通过矩阵快速幂大幅降低计算次数，精准得到斐波那契数取模后的结果。

总结

核心逻辑：将斐波那契递推转化为矩阵幂运算，利用快速幂降低时间复杂度。
关键操作：实现矩阵乘法和快速幂函数，对变换矩阵进行( k − 2 ) (k-2)(k−2)次幂运算。
结果计算：通过矩阵幂结果推导F k F_kFk，并对1 e 9 + 7 1e9+71e9+7取模输出。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pii;constll N=1e6+10;constll p=1e9+7;vtmul(vt a,vt b){vtres(a.size(),vector<ll>(b[0].size()));for(ll i=0;i<a.size();i++){for(ll j=0;j<b[0].size();j++){for(ll k=0;k<a[0].size();k++)res[i][j]=(res[i][j]+a[i][k]*b[k][j])%p;}}returnres;}vtqmi(vt a,ll b){vtres(a.size(),vector<ll>(a.size()));for(ll i=0;i<a.size();i++)res[i][i]=1;while(b){if(b&1)res=mul(res,a);a=mul(a,a);b>>=1;}returnres;}intmain(){ll k;cin>>k;if(k==1){cout<<1<<endl;return0;}vttmp(2,vector<ll>(2));tmp[1][0]=tmp[0][1]=tmp[1][1]=1;tmp=qmi(tmp,k-2);cout<<(tmp[0][1]+tmp[1][1])%p<<endl;return0;}