这个题我这么做为什么要调用 ksm(n-1) ?
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define pre(i,l,r) for(int i=l;i>=r;--i)
const int mod=1e9+7;
const int N=10;
struct matrix{
int c[N][N];
void clear(){
rep(i,1,3) rep(j,1,3) c[i][j]=0;
}
};
matrix operator ^(const matrix &a,const matrix &b){
matrix ans;ans.clear();
rep(i,1,3){
rep(j,1,3){
rep(k,1,3){
ans.c[i][j]+=a.c[i][k]*b.c[k][j];
ans.c[i][j]%=mod;
}
}
}
return ans;
}
int ksm(int y){
matrix ans;ans.clear();
matrix x;x.clear();
x.c[1][1]=1;x.c[1][3]=1;
x.c[2][1]=1;x.c[3][2]=1;
ans.c[1][1]=1;ans.c[2][1]=1;
ans.c[3][1]=1;
while(y){
if(y&1){
ans=ans^x;
}
x=x^x;y>>=1;
}
return ans.c[1][1];
}
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t,n;
cin>>t;
rep(i,1,t){
cin>>n;
if(n<=3){
cout<<1<<'\n';
}else cout<<ksm(n-1)<<'\n';
}
return 0;
}