@zzzc18
2017-11-09T11:49:02.000000Z
字数 900
阅读 860
模板库
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL n;
const LL MOD = 1e9+7;
struct Matrix{
LL mat[5][5];
Matrix(){
memset(mat,0,sizeof(mat));
}
}BASE,A;
Matrix operator * (const Matrix &X,const Matrix &Y){
Matrix re;
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
for(int k=1;k<=3;k++){
re.mat[i][j]+=X.mat[i][k]*Y.mat[k][j]%MOD;
re.mat[i][j]%=MOD;
}
}
}
return re;
}
void DEBUG(Matrix P){
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
printf("%d ",P.mat[i][j]);
}
puts("");
}
}
Matrix qpow(const Matrix &x,LL k){
Matrix mul=x;
Matrix re;
re.mat[1][1]=re.mat[2][2]=re.mat[3][3]=1;
for(LL i=1;i<=k;i<<=1){
if(i&k)
re=mul*re;
mul=mul*mul;
}
return re;
}
int main(){
BASE.mat[1][1]=1;
BASE.mat[1][3]=1;
BASE.mat[2][1]=1;
BASE.mat[3][2]=1;
A.mat[1][1]=A.mat[2][1]=A.mat[3][1]=1;
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%lld",&n);
if(n<=3)
puts("1");
else
printf("%lld\n",(qpow(BASE,n-3)*A).mat[1][1]);
}
return 0;
}