简介

矩阵快速幂能将 $O(n)$ 的线性递推优化成 $O(\log n)$。

矩阵

矩阵相当于二维数组。

• 矩阵 $A$ 有 $m$ 行 $n$ 列，称为 $m\times n$ 矩阵，简记为 $A_{mn}$；
• 矩阵 $A$ 第 $i$ 行 $j$ 列的元素写作 $a_{ij}$。

$$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right]$$

单位矩阵

主对角线上的元素都为 $1$，其余元素为 $0$ 的 $n\times n$ 矩阵称为 $n$ 阶单位矩阵，记作 $I_n$ 或 $E_n$。

$$I_n=\left[\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ 0& 1& 0& \cdots & 0\\ 0& 0& 1& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 1\end{array}\right]$$

矩阵加减法

矩阵的加减法就是将两个矩阵对应位置上的元素相加减。

矩阵乘法

定义矩阵 $A\times B=C$：

• 必须满足 $A$ 的列数 $=$ $B$ 的行数；
• $A_{mr}\times B_{rn}$ 会得到一个 $m\times n$ 矩阵 $C_{mn}$；
• $C=A\times B$ 的每个元素为$$c_{ij}=\sum _{k=1}^r{a}_{ik}\cdot b_{kj}$$

任意矩阵乘 $I_n$ 都等于它本身。

WARNING

• 矩阵乘法满足结合律，不满足交换律；
• 只有行数和列数相等的矩阵才能进行乘幂运算。

矩阵快速幂

基于 快速幂 的思想求 $n$ 阶矩阵的 $x$ 次方。时间复杂度：$O(n^3\log x)$。

矩阵运算可能需要 高精度 或取模。

const int N = 101; // 矩阵的行数和列数

struct matrix {
    int at[N][N];
    matrix() { memset(at, 0, sizeof at); }
    int* operator[](int key) { return at[key]; }
};

matrix operator *(matrix a, matrix b) { // 矩阵 A × 矩阵 B
    matrix c;
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            for (int k = 0; k < N; k ++)
                c[i][j] += a[i][k] * b[k][j];
    return c;
}

matrix operator ^(matrix a, int x) {    // 矩阵 A 的 x 次方
    matrix res;
    for (int i = 0; i < N; i ++)        // 初始化为单位矩阵
        res[i][i] = 1;
    while(x) {
        if(x % 2) res = res * a;
        a = a * a, x /= 2;
    }
    return res;
}

应用

若已知 $f(1),f(2)$，且存在矩阵 $A$，使得对于任意 $n$ 都有

$$A\times \left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$

就可以推出 $f(n)$ 的值。

$$\left(A^{n-2}\right)\times \left[\begin{array}{c}f(2)\\ f(1)\end{array}\right]=\left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]$$

可用矩阵快速幂求 $A^{n-2}$。时间复杂度：$O(\log n)$。

例 1

求斐波那契数列的第 $n$ 项 $f(n)$（$n\ge {10}^{12}$）。

$$f(n)=\{\begin{array}{ll}1& n=1,2\\ f(n-1)+f(n-2)& n\ge 3\end{array}$$

设矩阵 $A=\left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right]$ 满足

$$\left[\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right]\times \left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\end{array}\right]$$

即

$$\{\begin{array}{lll}f(n+1)& =& a_{11}\cdot f(n)+a_{12}\cdot f(n-1)\\ f(n)& =& a_{21}\cdot f(n)+a_{22}\cdot f(n-1)\end{array}$$

解得

$$\{\begin{array}{ll}{a}_{11}=1& a_{12}=1\\ a_{21}=1& a_{22}=0\end{array},A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$

因此

$${\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{n-2}\times \left[\begin{array}{c}f(2)\\ f(1)\end{array}\right]=\left[\begin{array}{c}f(n)\\ f(n-1)\end{array}\right]$$

将 $f(1)=f(2)=1$ 代入即可。

int main() {
    matrix A;
    A[1][1] = 1, A[1][2] = 1;
    A[2][1] = 1, A[2][2] = 0;

    matrix B;
    B[1][1]	= 1;	// f(1) = 1
    B[2][1] = 1;	// f(2) = 1

    cin >> n;
    B = (A ^ (n - 2)) * B;
    cout << B[1][1];
}

例 2

求数列的第 $n$ 项 $f(n)$（$n\ge {10}^{12}$）。

$$f(n)=\{\begin{array}{ll}1& n=1,2\\ f(n-1)+f(n-2)+n-1& n\ge 3\end{array}$$

设 $4$ 阶矩阵 $A$ 满足

$$\left[\begin{array}{cccc}{a}_{11}& a_{12}& a_{13}& a_{14}\\ a_{21}& a_{22}& a_{23}& a_{24}\\ a_{31}& a_{32}& a_{33}& a_{34}\\ a_{41}& a_{42}& a_{43}& a_{44}\end{array}\right]\times \left[\begin{array}{c}f(n)\\ f(n-1)\\ n\\ 1\end{array}\right]=\left[\begin{array}{c}f(n+1)\\ f(n)\\ n+1\\ 1\end{array}\right]$$

解得

$$A=\left[\begin{array}{cccc}1& 1& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 1& 1\\ 0& 0& 0& 1\end{array}\right]$$