波斐契那数列【牛客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^9+7)anmod(109+7)的值。
输入描述：
第一行输入整数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^9+7109+7）。
示例1
输入：
3 6 8 10输出：
4 9 19解题思路
本题核心是通过矩阵快速幂求解高阶线性递推数列，将波斐契那数列的递推式a x = a x − 1 + a x − 3 a_x=a_{x-1}+a_{x-3}ax=ax−1+ax−3转化为矩阵幂运算：构造变换矩阵[ 1 0 1 1 0 0 0 1 0 ] \begin{bmatrix}1&0&1\\1&0&0\\0&1&0\end{bmatrix}110001100，使得[ 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}axax−1ax−2=变换矩阵×ax−1ax−2ax−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 1e9+7anmod1e9+7。该方法时间复杂度为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，避免无效的矩阵运算。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pii;constll N=1e6+10;constll p=1e9+7;voidmul(ll a[3][3],ll b[3][3]){ll c[3][3]={0};for(ll i=0;i<3;i++)for(ll j=0;j<3;j++)for(ll k=0;k<3;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(n&1)mul(res,a);mul(a,a);n>>=1;}returnres[0][0];}voidsolve(){ll n;cin>>n;if(n<=2)cout<<"1"<<endl;elsecout<<f(n-1)<<endl;}intmain(){ll T;cin>>T;while(T--)solve();return0;}