矩阵快速幂

模板题：洛谷p1939

code：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5,mod=1e9+7;
int n,siz=3;
struct matrix{LL m[N][N];//构造函数matrix(){memset(m,0,sizeof m);}//重载*运算符matrix operator*(const matrix& B)const{matrix C;for(int i=1;i<=siz;i++)for(int j=1;j<=siz;j++)for(int k=1;k<=siz;k++)C.m[i][j]=(C.m[i][j]+m[i][k]*B.m[k][j])%mod;return C;}
};matrix qpow(matrix A,LL b){matrix RET;RET.m[1][1]=RET.m[2][2]=RET.m[3][3]=1;while(b){if(b&1)RET=RET*A;b>>=1;A=A*A;}return RET;
}int main(){cin.tie(nullptr)->sync_with_stdio(false);matrix A,RET,B;A.m[1][1]=A.m[1][2]=A.m[2][3]=A.m[3][1]=1;B.m[1][1]=B.m[1][2]=B.m[1][3]=1;int T;cin>>T;while(T--){cin>>n;if(n==1||n==2||n==3){cout<<1<<endl;continue;}RET=B*qpow(A,n-3);cout<<RET.m[1][1]<<'\n';}return 0;
}