矩阵加速算法：使用矩阵加速数列递推式的计算。

构造矩阵形式递推式

例如递推式：

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

如果直接用这个多项式形式递推式来进行递推，时间复杂度为：$O(n)$，接下来的操作就是为了加速这个过程。

我们列出递推式对应的方程组：

$$ \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} $$

矩阵快速幂

由于矩阵乘法也满足 $M^{2n}=(M^2)^n$，因此类比数乘快速幂，矩阵也可以用快速幂算法，只需将数乘换成矩阵乘法即可。

对于上述例子：

$$ \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} $$

通过快速幂来处理 $M^n$，时间复杂度为 $O(\log n)$，实现了递推计算的加速。

模板

$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;
}