网站建设营销排名方案,个人网站备案地址,用花生壳免费域名做公司网站,漳州做网站公司斐波那契数列 时间限制#xff1a;1秒 空间限制#xff1a;256M 知识点#xff1a; 递归 基础数学 网页链接 牛客tracker 牛客tracker 每日一题#xff0c;完成每日打卡#xff0c;即可获得牛币。获得相应数量的牛币#xff0c;能在【牛币兑换中心】#xff…斐波那契数列时间限制1秒 空间限制256M知识点递归基础数学网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述斐波那契数列Fibonacci Sequence定义如下F 1 F 2 1 F_1F_21F1​F2​1对于i ≧ 3 i≧3i≧3有F i F i − 1 F i − 2 F_iF_{i−1}F_{i−2}Fi​Fi−1​Fi−2​。给定一个正整数k kk请你输出F k F_kFk​的值。由于这个结果可能很大你只需要输出这个结果对( 10 9 7 ) (10^97)(1097)取模后的结果即可。输入描述在一行上输入一个整数k ( 1 ≦ k ≦ 10 6 ) k(1≦k≦10^6)k(1≦k≦106)。输出描述输出一个整数表示F k m o d ( 10 9 7 ) F_k \mod\ (10^97)Fk​mod(1097)的值。示例1输入19输出4181解题思路本题采用矩阵快速幂高效计算斐波那契数列第k kk项核心是将斐波那契递推式转化为矩阵幂运算斐波那契递推式F i F i − 1 F i − 2 F_iF_{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}11\\10\end{bmatrix}^{i-2} \begin{bmatrix}F_2\\F_1\end{bmatrix}[Fi​Fi−1​​][11​10​]i−2[F2​F1​​]先定义矩阵乘法和快速幂函数初始化变换矩阵[ 1 1 1 0 ] \begin{bmatrix}11\\10\end{bmatrix}[11​10​]对其进行( 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 1e97Fk​(tmp[0][1]tmp[1][1])mod1e97。该方法时间复杂度为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 1e971e97取模输出。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpii;constll N1e610;constll p1e97;vtmul(vt a,vt b){vtres(a.size(),vectorll(b[0].size()));for(ll i0;ia.size();i){for(ll j0;jb[0].size();j){for(ll k0;ka[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(),vectorll(a.size()));for(ll i0;ia.size();i)res[i][i]1;while(b){if(b1)resmul(res,a);amul(a,a);b1;}returnres;}intmain(){ll k;cink;if(k1){cout1endl;return0;}vttmp(2,vectorll(2));tmp[1][0]tmp[0][1]tmp[1][1]1;tmpqmi(tmp,k-2);cout(tmp[0][1]tmp[1][1])%pendl;return0;}