P1939【模板】矩阵加速（数列）

P1939【模板】矩阵加速（数列）
难受就难受在a[i-3],这样的话让k=3就好了。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<set>

 #include<cstring>

 #define mod 1000000007

 #define For(i,a,b) for(register long long i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 //by war

 //2017.10.26

 using namespace std;

 long long k,t;

 struct matrix

 {

     long long a[];

     long long b[][];

     matrix operator *(const matrix&c)const

     {

         matrix r;

         For(i,,)

           For(j,,)

           {

              r.b[i][j]=;

              For(k,,)

             r.b[i][j]=(r.b[i][j]+(b[i][k]*c.b[k][j])%mod)%mod;

           }

         return r;

     }

 }a;

 void in(long long &x)

 {

     long long y=;

     char c=g();x=;

     while(c<''||c>'')

     {

     if(c=='-')

     y=-;

     c=g();

     }

     while(c<=''&&c>='')x=x*+c-'',c=g();

     x*=y;

 }

 void o(long long x)

 {

     if(x<)

     {

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 matrix ksm(matrix a,long long b)

 {

     matrix r=a;b--;

     if(b==)

     return r;

     while(b%==)

     {

         a=a*a;

         b>>=;

     }

     while(b>)

     {

         if(b%==)

         r=r*a;

         a=a*a;

         b>>=;

     }

     return r;

 }

 int main()

 {

     in(t);

     while(t--)

     {

     in(k);

     if(k==||k==||k==)

     {

         o(),p('\n');

     }

     else

     {

     a.a[]=;

     a.a[]=;

     a.a[]=;

     a.b[][]=;

     a.b[][]=;

     a.b[][]=;

     a.b[][]=;

     a.b[][]=;

     a.b[][]=;

     a.b[][]=;

     a.b[][]=;

     a.b[][]=;

     matrix r,ans;

     r=ksm(a,k-);

     for(register int i=;i<=;i++)

           For(j,,)

           {

              ans.a[i]=;

              For(k,,)

             ans.a[i]=(ans.a[i]+(a.a[i]*r.b[k][j])%mod)%mod;

           }

     For(i,,)

     o((ans.a[i]%mod+mod)%mod),p('\n');

     }

     }

      return ;

 }