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

矩阵加速的难点就在于构造转移矩阵。

根据题目的提示显然我们的初始矩阵为

$\begin{bmatrix}1\\1\\1\end{bmatrix}$

假设我们当前矩阵需要求的矩阵为 $\begin{bmatrix}a_i\\a_{i-1}\\a_{i-2}\end{bmatrix}$

根据递推公式有 $\begin{cases}a_i\ \ \ =a_{i-1}\times1+a_{i-2}\times0+a_{i-3}\times1\\a_{i-1}=a_{i-1}\times1+a_{i-2}\times0+a_{i-3}\times0\\a_{i-2}=a_{i-1}\times0+a_{i-2}\times1+a_{i-3}\times0\end{cases}$

观察可得 $\begin{bmatrix}1,0,1\\1,0,0\\0,1,0\end{bmatrix}$ 即为状态转移矩阵。

所以答案为

$ans=\begin{bmatrix}a_i\\a_{i-1}\\a_{i-2}\end{bmatrix}=\begin{bmatrix}1,0,1\\1,0,0\\0,1,0\end{bmatrix}^{n-3}.\begin{bmatrix}a_1\\a_2\\a_3\end{bmatrix}\quad (n>3)$

$else\quad ans=\begin{bmatrix}1\\1\\1\end{bmatrix}$

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
ll n,t;
struct Mat{
    ll a[4][4];
    Mat operator * (const Mat & mat)const{ //重载乘号 
        Mat ans;
        memset(ans.a,0,sizeof ans.a);//初始化 
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                for(int k=1;k<=3;k++)
                    ans.a[i][j]=(ans.a[i][j]+a[i][k]*mat.a[k][j]%mod)%mod;
        return ans; 
    }
}m;
Mat ksm(Mat m,ll x){ //矩阵快速幂板子 
     Mat ans;
     memset(ans.a,0,sizeof ans.a); 
     ans.a[1][1]=ans.a[2][2]=ans.a[3][3]=1;
     while(x){
          if(x&1) ans=m*ans;
          m=m*m;
          x>>=1;
     }
     return ans;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        if(n<=3){ //特判.防止n-3<=0. 
            puts("1");
            continue;
        }
    memset(m.a,0,sizeof m.a);
    m.a[1][1]=m.a[1][3]=m.a[2][1]=m.a[3][2]=1;//初始化 
     m=ksm(m,n-3);
     ll ans=(m.a[1][1]+m.a[2][1]+m.a[3][1])%mod;
     printf("%lld\n",ans);
    }
    return 0;
}