矩阵加速数列计算

a[1]=a[2]=a[3]=1

a[x]=a[x-3]+a[x-1] (x>3)

求a数列的第n项对1000000007（10^9+7）取余的值。

显然可以推出：$egin{pmatrix}a_x&a_{x+1}&a_{x+2}end{pmatrix}*egin{pmatrix}0&0&1\1&0&0\0&1&1\end{pmatrix}=egin{pmatrix}a_{x+1}&a_{x+2}&a_{x+3}end{pmatrix}$

然后矩阵运算即可。。

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 typedef long long LL;
 6 const int mod=1e9+7;
 7 int T, n;
 8 LL tmp[3][3]={{0,0,1},{1,0,0},{0,1,1}};
 9 
10 struct Matrix33{
11     LL mat[3][3];
12     Matrix33 operator *(Matrix33 b){
13         Matrix33 m;
14         for (int i=0; i<3; ++i) for (int j=0; j<3; ++j){
15             m.mat[i][j]=0;
16             for (int k=0; k<3; ++k)
17                 //LL忘记了
18                 m.mat[i][j]=(m.mat[i][j]+(mat[i][k]*b.mat[k][j]%mod))%mod;
19         }
20         return m;
21     }
22     //为什么没有*=，因为这个的开销和复制差不了多少
23 }beg, unit, plus;
24 
25 Matrix33 get_mat(int n){
26     memcpy(plus.mat, tmp, sizeof(tmp));
27     Matrix33 ans=unit;
28     while (n){
29         if (n&1) ans=ans*plus;
30         plus=plus*plus;
31         n>>=1;
32     }
33     return ans;
34 }
35 
36 int main(){
37     unit.mat[0][0]=unit.mat[1][1]=unit.mat[2][2]=1;
38     beg.mat[0][0]=beg.mat[0][1]=beg.mat[0][2]=1;
39     scanf("%d", &T);
40     for (int tt=0; tt<T; ++tt){
41         scanf("%d", &n);
42         if (n<4) printf("1
");
43         else printf("%lld
", (beg*get_mat(n-3)).mat[0][2]);
44     }
45     return 0;
46 }