跳转至

矩阵乘法

约 466 个字    20 行代码  预计阅读时间 2 分钟

计算过程

设 \(A\) 矩阵与 \(B\) 矩阵相乘得 \(C\) 矩阵，则可记为：

\[ AB = C \]

其中，\(C\) 矩阵的第 \(i\) 行第 \(j\) 列元素可以表示为：

\[ C_{i,j} = \sum_{k = 1}^{M}A_{i, k}B_{k, j} \]

\(C\) 矩阵的行数等于 \(A\) 矩阵的行数，而 \(C\) 矩阵的列数等于 \(B\) 矩阵的列数。

简记：左行右列

公式看不懂？举个例子：

设 \(A = \begin{bmatrix} 1 & 3 & 6 \\ 2 & 4 & 5 \end{bmatrix}, B = \begin{bmatrix} 2 & 5 \\ 6 & 3 \\ 1 & 4 \end{bmatrix}\)，\(A\) 与 \(B\) 相乘得 \(C\)。

则 \(C_{1, 1} = 1 \times 2 + 3 \times 6 + 6 \times 1 = 26\)，于是：

\[ C = \begin{bmatrix} 26 & ? \\ ? & ? \end{bmatrix} \]

同理类推，\(C_{1, 2} = 1 \times 5 + 3 \times 3 + 6 \times 4 = 38\)，于是：

\[ C = \begin{bmatrix} 26 & 38 \\ ? & ? \end{bmatrix} \]

\(C_{2, 1} = 2 \times 2 + 4 \times 6 + 5 \times 1 = 33\)

\[ C = \begin{bmatrix} 26 & 38 \\ 33 & ? \end{bmatrix} \]

最后我们就能推出来：

\[ C = \begin{bmatrix} 26 & 38 \\ 33 & 42 \end{bmatrix} \]

是不是非常神奇 qwq。

参考代码

struct Mat
{
    int arr[SIZE][SIZE];
    Mat() { memset(arr, 0, sizeof arr); }
    Mat operator*(const Mat& T) const
    {
        Mat res;
        int tmp;
        for (int i = 0; i < SIZE; ++i)
            for (int k = 0; k < SIZE; ++k) {
                tmp = arr[i][k];
                for (int j = 0; j < SIZE; ++j)
                    res.arr[i][j] += T.arr[k][j] * tmp, res.arr[i][j] %= MOD;
            }
        return res;
    }
}A;

/* main() */
Mat C = A * B;

应用

矩阵加速递归（斐波那契数列）

在 斐波那契数列 (Fibonacci Sequence) 中，设 \(F_i\) 为第 \(i\) 项的值，则 \(F_1 = F_2 = 1, F_i = F_{i - 1} + F_{i - 2} (i \geq 3)\)。

那么常规方法就是写 \(for\) 循环一直递归下去，但很显然数量级一大就不行了。

我们定义 \(\texttt{base}\) 矩阵为 \(\begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}\)，\(\texttt{ans}\) 矩阵为 \(\begin{bmatrix}F_n & F_{n - 1} \end{bmatrix}\)，为其赋初值为 \(\begin{bmatrix}F_2 & F_1 \end{bmatrix} = \begin{bmatrix}1 & 1 \end{bmatrix}\)。

可以推得，

\[ \begin{bmatrix}F_{n - 1} & F_{n - 2} \end{bmatrix} \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix} = \begin{bmatrix}F_{n - 1} + F_{n - 2} & F_{n - 1} \end{bmatrix} = \begin{bmatrix}F_n & F_{n - 1} \end{bmatrix} \]

于是，\(F_n\) 这个元素就等于 \(\texttt{ans}\texttt{base}^{n - 2}\) 的值。

为啥是 \(n - 2\) 次方而不是 \(n\) 次方呢，因为 \(F_1\) 和 \(F_2\) 的值本身就是已知的，不需要被计算出来。

评论