题目描述
a[1]=a[2]=a[3]=1a[1]=a[2]=a[3]=1
a[x]=a[x−3]+a[x−1](x>3)a[x]=a[x−3]+a[x−1](x>3)
求aa数列的第nn项对10000000071000000007（109+7109+7）取余的值。
输入描述 第一行一个整数TT，表示询问个数。
以下TT行，每行一个正整数nn。
输出描述
每行输出一个非负整数表示答案。
样例输入
3
6
8
10样例输出
4
9
19时间限制、数据范围及描述
时间：1s 空间：256M
对于30%30%的数据 n≤100n≤100；
对于60%60%的数据 n≤2∗107n≤2∗107；
对于100%100%的数据 T≤100T≤100，n≤2∗109n≤2∗109；
除了那个优化的小技巧，劳资的矩阵快速幂一点都没忘，结果踏马还搞了半天才搞好
1 #include "bits/stdc++.h" 2 using namespace std; 3 typedef long long LL; 4 const int mod=1000000007; 5 int t; 6 int n; 7 struct Mat{ 8 int x,y; 9 LL mat[5][5]; 10 Mat(){x=y=0;memset(mat,0,sizeof(mat));} 11 Mat operator *(const Mat &tt) { 12 int i,j,k; 13 Mat an; 14 an.x=x,an.y=tt.y; 15 for (k=1;k<=y;k++){ 16 for (i=1;i<=an.x;i++){ 17 if (mat[i][k]){ 18 for (j=1;j<=an.y;j++){ 19 an.mat[i][j]=(an.mat[i][j]+mat[i][k]*tt.mat[k][j])%mod; 20 } 21 } 22 } 23 } 24 return an; 25 } 26 }; 27 Mat ksm(Mat tt,int x){ 28 int i,j; 29 Mat an; 30 an.x=an.y=3; 31 an.mat[1][1]=an.mat[2][2]=an.mat[3][3]=1; 32 while (x){ 33 if (x%2) an=tt*an;//注意:不能写成an*tt 34 tt=tt*tt; 35 x/=2; 36 } 37 return an; 38 } 39 int main(){ 40 freopen ("string.in","r",stdin); 41 freopen ("string.out","w",stdout); 42 int i,j; 43 scanf("%d",&t); 44 while (t--){ 45 scanf("%d",&n); 46 if (n<=3) {puts("1");continue;} 47 int x=(n-1)/3+1,y=n%3;y=(y==0?3:y); 48 Mat ans,mm,nn; 49 mm.x=mm.y=3; 50 mm.mat[1][1]=mm.mat[1][3]=mm.mat[2][1]=mm.mat[2][2]=mm.mat[2][3]=mm.mat[3][1]=mm.mat[3][2]=1; 51 mm.mat[3][3]=2; 52 nn.x=3,nn.y=1; 53 nn.mat[1][1]=nn.mat[2][1]=nn.mat[3][1]=1; 54 ans=ksm(mm,x-1)*nn;//注意,理由同上 55 printf("%lld ",ans.mat[y][1]); 56 } 57 return 0; 58 }