算法 | 矩阵加速算法

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

构造矩阵形式递推式

例如递推式：

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

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

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

$$\{\begin{array}{lllll}{a}_n& =& a_{n-1}& & +a_{n-3}\\ a_{n-1}& =& a_{n-1}& \\ a_{n-2}& =& & +a_{n-2}\end{array}$$

写成矩阵形式：

$$\left[\begin{array}{c}{a}_n\\ a_{n-1}\\ a_{n-2}\end{array}\right]=\left[\begin{array}{ccc}1& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right]\left[\begin{array}{c}{a}_{n-1}\\ a_{n-2}\\ a_{n-3}\end{array}\right]$$

那么即可得到每一项：

$$\left[\begin{array}{c}{a}_n\\ a_{n-1}\\ a_{n-2}\end{array}\right]={\left[\begin{array}{ccc}1& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right]}^{n-3}\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$$

矩阵快速幂

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

对于上述例子：

$$\left[\begin{array}{c}{a}_{n+3}\\ a_{n+2}\\ a_{n+1}\end{array}\right]=M^n\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right],\mathrm{其}\mathrm{中}M=\left[\begin{array}{ccc}1& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right]$$

通过快速幂来处理 $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;
}