这里，我们定义目标矩阵为
\[A_n =
\begin{bmatrix}
a_n \\
a_{n-1} \\
a_{n-2} \\
\end{bmatrix}
\]
那么我们思考一下它怎么从 \(A_{n - 1}\) 推导而来
\[A_{n-1} =
\begin{bmatrix}
a_{n - 1} \\
a_{n - 2} \\
a_{n - 3} \\
\end{bmatrix}
\]
由题有：
\[\begin{cases}
a_n = 1 \times a_{n-1} + 0 \times a_{n-2} + 1 \times a_{n-3} \\
a_{n-1} = 1\times a_{n-1} + 0 \times a_{n - 2} + 0 \times a_{n - 3} \\
a_{n-2} = 0\times a_{n-1} + 1 \times a_{n - 2} + 0 \times a_{n - 3}
\end{cases}
\]
所以我们的转移矩阵就是
\[T =
\begin{bmatrix}
1 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{bmatrix}
\]
注意：矩阵乘法一般不满足分配律，所以相乘时顺序不要搞错。
code：
#include<bits/stdc++.h>
using namespace std;
#define mo 1000000007
#define int long long
struct juzhen{
int a[5][5];
int n, m;
juzhen(){ //矩阵初始化
n = m = 0;
fill(a[0], a[0] + 5 * 5, 0);
}
void unit(int kn){ //构建单位矩阵
n = m = kn;
for(int i = 1; i <= n; i ++) a[i][i] = 1;
}
void init(){ //对于每个题目的初始矩阵
n = 3, m = 1;
a[1][1] = a[2][1] = a[3][1] = 1;
}
void zy(){ //每个题目的转移矩阵
n = 3, m = 3;
a[1][1] = a[1][3] = a[2][1] = a[3][2] = 1;
}
void out(){ //输出矩阵，方便查错
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cout << a[i][j] << " ";
}cout << endl;
}
}
juzhen operator *(const juzhen &b){
juzhen res;
res.n = n, res.m = b.m;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= b.m; j ++){
for(int k = 1; k <= m; k ++){
res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j] % mo) % mo;
}
}
}
return res;
}
};
juzhen qsm(juzhen base, int k){
juzhen res;
res.unit(3);
while(k){
if(k & 1) res = res * base;
base = base * base;
k >>= 1;
}
return res;
}
int n;
signed main(){
//freopen("shuju.in", "r", stdin);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int TN;
cin >> TN;
while(TN--){
cin >> n;
if(n <= 3) cout << 1 << endl;
else{
juzhen ans, t;
ans.init();
t.zy();
// t.out();
// ans.out();
ans = qsm(t, n - 3) * ans;
cout << ans.a[1][1] << endl;
}
}
return 0;
}