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

波斐契那数列时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述定义数列a x {a_x}ax​满足a x { 1 , x ∈ { 1 , 2 , 3 } ; a x − 1 a x − 3 , x ≧ 4 a_x \begin{cases} 1,\quad x∈\{1,2,3 \};\\ a_{x-1}a_{x-3}, \quad x≧4 \end{cases}ax​{1,x∈{1,2,3};ax−1​ax−3​,x≧4​给定n nn请求出a n m o d ( 10 9 7 ) a_n \mod (10^97)an​mod(1097)的值。输入描述第一行输入整数T ( 1 ≦ T ≦ 100 ) T (1≦T≦100)T(1≦T≦100)表示询问数量。接下来T TT行每行一个整数n ( 1 ≦ n ≦ 2 × 10 9 ) n (1≦n≦2×10^9)n(1≦n≦2×109)。输出描述对于每个询问在一行上输出a n a_nan​的值取模10 9 7 10^971097。示例1输入3 6 8 10输出4 9 19解题思路本题核心是通过矩阵快速幂求解高阶线性递推数列将波斐契那数列的递推式a x a x − 1 a x − 3 a_xa_{x-1}a_{x-3}ax​ax−1​ax−3​转化为矩阵幂运算构造变换矩阵[ 1 0 1 1 0 0 0 1 0 ] \begin{bmatrix}101\\100\\010\end{bmatrix}​110​001​100​​使得[ a x a x − 1 a x − 2 ] 变换矩阵 × [ a x − 1 a x − 2 a x − 3 ] \begin{bmatrix}a_x\\a_{x-1}\\a_{x-2}\end{bmatrix} 变换矩阵 × \begin{bmatrix}a_{x-1}\\a_{x-2}\\a_{x-3}\end{bmatrix}​ax​ax−1​ax−2​​​变换矩阵×​ax−1​ax−2​ax−3​​​定义矩阵乘法函数实现快速幂运算以降低时间复杂度对于输入的n nn若n ≤ 3 n≤3n≤3直接返回1 11否则对变换矩阵进行( n − 3 ) (n-3)(n−3)次快速幂运算代码中简化为( n − 1 ) (n-1)(n−1)次最终通过矩阵结果计算a n m o d 1 e 9 7 a_n \mod 1e97an​mod1e97。该方法时间复杂度为O ( log ⁡ n ) O(\log n)O(logn)适配n ≤ 2 × 10 9 n≤2×10^9n≤2×109、T ≤ 100 T≤100T≤100的规模通过矩阵快速幂高效求解超大项的递推值。总结核心逻辑将三阶线性递推转化为3 × 3 3×33×3矩阵乘法利用快速幂将时间复杂度降至对数级。关键操作实现矩阵乘法和快速幂通过矩阵幂运算推导递推数列的第n nn项。边界处理n ≤ 3 n≤3n≤3时直接返回初始值1 11避免无效的矩阵运算。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpii;constll N1e610;constll p1e97;voidmul(ll a[3][3],ll b[3][3]){ll c[3][3]{0};for(ll i0;i3;i)for(ll j0;j3;j)for(ll k0;k3;k)c[i][j](c[i][j]a[i][k]*b[k][j])%p;memcpy(a,c,sizeof(c));}llf(ll n){ll a[3][3]{1,0,1,1,0,0,0,1,0};ll res[3][3]{1,0,0,0,1,0,0,0,1};while(n){if(n1)mul(res,a);mul(a,a);n1;}returnres[0][0];}voidsolve(){ll n;cinn;if(n2)cout1endl;elsecoutf(n-1)endl;}intmain(){ll T;cinT;while(T--)solve();return0;}