## 构造矩阵形式递推式

$$a_n=a_{n-1}+a_{n-3},\ 其中\ a_1=a_2=a_3=1$$

$$\begin{cases} a_n&=&a_{n-1}&&+a_{n-3}\\ a_{n-1}&=&a_{n-1}&\\ a_{n-2}&=&&+a_{n-2} \end{cases}$$

$$\begin{bmatrix} a_{n}\\ a_{n-1}\\ a_{n-2} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} a_{n-1}\\ a_{n-2}\\ a_{n-3} \end{bmatrix}$$

$$\begin{bmatrix} a_{n}\\ a_{n-1}\\ a_{n-2} \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix}^{n-3} \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}$$

## 矩阵快速幂

$$\begin{bmatrix} a_{n+3}\\ a_{n+2}\\ a_{n+1} \end{bmatrix} = M^{n} \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} ,\ 其中\ M=\begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 0\\ 0 & 1 & 0 \end{bmatrix}$$

## 模板

$n$ 阶方阵乘法：

vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod)
{
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
res[i][j] = (res[i][j] + a[i][k] * b[k][j] % mod) % mod;
return res;
}

vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod)
{
int n = a.size();
vector<vector<ll>> res(n, vector<ll>(n));
for (int i = 0; i < n; i++)
res[i][i] = 1;
while (b)
{
if (b % 2)
res = mat_mul(res, a, mod);
a = mat_mul(a, a, mod);
b /= 2;
}
return res;
}