upd:现在推荐使用一个长度为 \(n\) 的一维向量。若状态矩阵 \(F\) 对下一时间的状态矩阵 \(F'\) 有影响，则 \(F'=FA\) 中的 转移矩阵 \(A\) 的赋值方法是：
若状态矩阵中的第 \(x\) 个数对下一单位时间的状态矩阵的第 \(y\) 个数有影响，则将转移矩阵的第 \(x\) 行第 \(y\) 列赋值为合适的数。
递推太慢，用矩阵加速。
有递推关系
\[f_i=a_{i-1}f_{i-1}+a_{i-2}f_{i-2}+\cdots+a_{i-k}f_{i-k}
\]
\]
若有目标矩阵 \(\boldsymbol{F}\) ：
\[\left[
\begin{matrix}
f_i \\
f_{i-1} \\
\vdots \\
f_{i-k+1}
\end{matrix}
\right]
\]
\begin{matrix}
f_i \\
f_{i-1} \\
\vdots \\
f_{i-k+1}
\end{matrix}
\right]
\]
与已得出的矩阵 \(\boldsymbol{F'}\) ：
\[\left[
\begin{matrix}
f_{i-1} \\
f_{i-2} \\
\vdots \\
f_{i-k}
\end{matrix}
\right]
\]
\begin{matrix}
f_{i-1} \\
f_{i-2} \\
\vdots \\
f_{i-k}
\end{matrix}
\right]
\]
则式子 \(\boldsymbol{F}=\boldsymbol{A}\boldsymbol{F'}\) 中的 $ \boldsymbol{A}$ 为：
\[\left[
\begin{matrix}
a_1 & a_2 & a_3 & \cdots & a_k \\
1 &0 & 0 & \cdots &0 \\
0 &1 & 0 & \cdots &0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1 & 0
\end{matrix}
\right]
\]
\begin{matrix}
a_1 & a_2 & a_3 & \cdots & a_k \\
1 &0 & 0 & \cdots &0 \\
0 &1 & 0 & \cdots &0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & 1 & 0
\end{matrix}
\right]
\]
从 \(\boldsymbol{F'}\) 变换到 \(\boldsymbol{F}\) 所需要的次数 $ i $ 即为 \(\boldsymbol{A}\) 的指数。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
int T;
ll n;
const ll mod=1e9+7;
struct Matrix{
ll num[5][5];
Matrix operator*(const Matrix &x)const{
Matrix res;
for(int i=1; i<=3; i++)
for(int j=1; j<=3; j++){
res.num[i][j] = 0;
for(int k=1; k<=3; k++)
res.num[i][j] = (res.num[i][j]+num[i][k]*x.num[k][j]%mod)%mod;
}
return res;
}
Matrix operator^(ll k)const{
Matrix res, x=*this;
memset(res.num, 0, sizeof(res.num));
for(int i=1; i<=3; i++) res.num[i][i] = 1;
//把res初始化成一个单位矩阵
while(k){
if(k&1) res = res * x;
x = x * x;
k >>= 1;
}
return res;
}
}a, b;
int main(){
cin>>T;
while(T--){
scanf("%lld", &n);
if(n<=3) printf("1\n");
else{
memset(a.num, 0, sizeof(a.num));
memset(b.num, 0, sizeof(b.num));
a.num[1][1] = a.num[1][3] = a.num[2][1] = a.num[3][2] = 1;
for(int i=1; i<=3; i++) b.num[i][1] = 1;
n -= 3;
a = a ^ n;
b = a * b;
//矩阵快速幂
printf("%lld\n", b.num[1][1]);
}
}
return 0;
}