很明显珂以构造初始矩阵 \(f\)。
\begin{bmatrix}
1\\
1\\
1
\end{bmatrix}
状态矩阵
\begin{bmatrix}
f_{n-1}\\
f_{n-2}\\
f_{n-3}
\end{bmatrix}
转移矩阵构造：
由于
\begin{cases}
f_n=f_{n-1}+f_{n-3}\\
\\
f_{n-1}=f_{n-1}\\
\\
f_{n-2}=f_{n-2}
\end{cases}
可以构造矩阵 \(p\)
\begin{bmatrix}
1 & 0 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}

然后答案=\(f\times p^{n-3}\) 的最上面一项

\(O((mnp)T\log n)=O(9T\log n)\)，可以通过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Matrix{
	int a[5][5];
	int n,m;
};
const int mod=1e9+7;
Matrix operator *(Matrix a,Matrix b){
	Matrix c;
	assert(a.m==b.n);
	c.n=a.n,c.m=b.m;
	for(int i=1;i<=c.n;i++){
		for(int j=1;j<=c.m;j++){
			int sum=0;
			for(int k=1;k<=a.m;k++)sum+=a.a[i][k]*b.a[k][j],sum%=mod;
			c.a[i][j]=sum;
		}
	}
	return c;
}
Matrix operator %(Matrix a,int b){
	for(int i=1;i<=a.n;i++){
		for(int j=1;j<=a.m;j++)a.a[i][j]%=b;
	}
	return a;
}
Matrix ksm(Matrix a,int b){
	if(b==1)return a;
	Matrix ans=ksm(a,b>>1);
	if(b&1)return ans*ans%mod*a%mod;
	else return ans*ans%mod;
}
Matrix f,p;
int T;
signed main(){
	f.n=3,f.m=1,f.a[1][1]=f.a[2][1]=f.a[3][1]=1;
	p.n=p.m=3;
	p.a[1][1]=1,p.a[1][2]=0,p.a[1][3]=1,p.a[2][1]=1,p.a[2][2]=0,p.a[2][3]=0,p.a[3][1]=0,p.a[3][2]=1,p.a[3][3]=0;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		if(n<=3)cout<<1<<endl;
		else cout<<(ksm(p,n-3)*f).a[1][1]<<endl;
	}
	return 0;
}