使用的矩阵连乘+2分幂，可以使题目中的lgN加大到10^6，N有多大不会算了

#include <stdio.h>
#define LL long long
#define N 8
void mult(LL a[N][N],LL b[N][N])//a*=b;
  {
      int c[N][N];
      for(int i=0;i<N;i++)
       for(int j=0;j<N;j++)
       {c[i][j]=0;
           for(int k=0;k<N;k++)
            c[i][j]+=a[i][k]*b[k][j];
       }
     for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
       a[i][j]=c[i][j];
}
void pow(LL a[N][N],int n)//a=a^n
 {
     LL c[N][N];
     for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
       if(i==j)c[i][j]=1;
       else c[i][j]=0;
     while(n)
      {
          if(n%2)mult(c,a);
          mult(a,a);
          n/=2;
      }
     for(int i=0;i<N;i++)
      for(int j=0;j<N;j++)
       a[i][j]=c[i][j];
 }
int main()
{
    int n;
    while(1)
     {
         scanf("%d",&n);
         if(n==-1)break;
         //if(n==0){printf("0\n");continue;}因为n=0时输出为1，所以+的特判。。结果反而错了。下面是状态转移的矩阵
         LL dp[N][N]={ {0,0,0,0,0,0,0,1},
                       {0,0,0,0,0,0,1,0},
                       {0,0,0,0,0,1,0,0},
                       {0,0,0,0,1,0,0,1},
                       {0,0,0,1,0,0,0,0},
                       {0,0,1,0,0,0,0,0},
                       {0,1,0,0,0,0,0,1},
                       {1,0,0,1,0,0,1,0}};

         pow(dp,n+2);
         printf("%I64d\n",dp[0][0]);
     }
}