題目描述 a[1]=a[2]=a[3]=1 a[x]=a[x-3]+a[x-1] (x>3) 求a數列的第n項對1000000007（10^9+7）取餘的值。 輸入輸出格式 輸入格式： 第一行一個整數T，表示詢問個數。 以下T行，每行一個正整數n。 輸出格式： 每行輸出一個非負整數表示答案。 輸入輸 ...
題目描述
a[1]=a[2]=a[3]=1
a[x]=a[x-3]+a[x-1] (x>3)
求a數列的第n項對1000000007（10^9+7）取餘的值。
輸入輸出格式
輸入格式：
第一行一個整數T，表示詢問個數。
以下T行，每行一個正整數n。
輸出格式：
每行輸出一個非負整數表示答案。
輸入輸出樣例
輸入樣例#1：3 6 8 10輸出樣例#1：
4 9 19
說明
對於30%的數據 n<=100；
對於60%的數據 n<=2*10^7；
對於100%的數據 T<=100，n<=2*10^9；
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 const int MAXN=101; 6 inline void read(int &n){char c='+';bool flag=0;n=0; 7 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar(); 8 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;} 9 struct matrix 10 { 11 long long m[11][11]; 12 int h,l;matrix(){memset(m,0,sizeof(m));h=l=0;} 13 }; 14 matrix ma; 15 int limit; 16 const int mod=1000000007; 17 matrix mul(matrix a,matrix b) 18 { 19 matrix c;c.h=c.l=3; 20 for(int k=0;k<a.l;k++) 21 for(int i=0;i<a.h;i++) 22 for(int j=0;j<b.l;j++) 23 c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j]))%mod; 24 return c; 25 } 26 matrix fast_martix_pow(matrix ma,int p) 27 { 28 matrix bg; 29 for(int i=0;i<3;i++) 30 for(int j=0;j<3;j++) 31 bg.m[i][j]=(i==j); 32 bg.h=bg.l=3; 33 while(p) 34 { 35 if(p&1) bg=mul(bg,ma); 36 ma=mul(ma,ma); 37 p>>=1; 38 } 39 return bg; 40 } 41 int main() 42 { 43 int T;read(T); 44 while(T--) 45 { 46 int m; 47 read(m); 48 if (m<=3&&m>0) {cout<<1<<endl; continue;} else if (m<=0) {cout<<0<<endl; continue;} 49 matrix a,b; 50 a.m[0][0]=1; 51 a.m[0][2]=1; 52 a.m[1][0]=1; 53 a.m[2][1]=1; 54 b.m[0][0]=1; 55 b.m[1][0]=1; 56 b.m[2][0]=1; 57 a.h=a.l=3; 58 b.h=3;b.l=1; 59 a=fast_martix_pow(a,m-3); 60 a=mul(a,b); 61 printf("%d\n",a.m[0][0]%mod); 62 } 63 return 0; 64 }
