就算告诉我是矩阵快速幂我也推不出递推式呀！！！

官方题解：

对于任意i>=1，当j>=3时，有通过归纳法可以得到 

进而推导出 

后来自己重新推导了一遍

 

 

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const ll Mod=1e9+7;const int msize=2;const int N=4;struct Mat{    ll mat[N][N];};Mat operator *(Mat a, Mat b){    Mat c;    memset(c.mat, 0, sizeof(c.mat));    for(int k = 0; k < msize; ++k)        for(int i = 0; i < msize; ++i)            if(a.mat[i][k])                for(int j = 0; j < msize; ++j)                    if(b.mat[k][j])                        c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod;    return c;}Mat operator ^(Mat a, ll k){    Mat c;    memset(c.mat,0,sizeof(c.mat));    for(int i = 0; i < msize; ++i)        c.mat[i][i]=1;    for(; k; k >>= 1)    {        if(k&1) c = c*a;        a = a*a;    }    return c;}Mat operator -(Mat a,Mat b){    for(int i=0; i