Loading... ## 前言 矩阵是线性代数的内容，在OI竞赛中有广泛运用。 常见知识点： - 矩阵乘法 - 矩阵快速幂 - 矩阵加速递推 <!--more--> ## 定义 - 矩阵: 类似一个$r * c$的二维数组。 - 方阵: 一个$n * n$的矩阵。 - 矩阵乘法: 将一个$a * c$的矩阵$A$和一个$c * b$的矩阵$B$相乘，得到一个$a * b$的矩阵$C$。 $C_{i,j} = \sum{A_{i, k} * B_{k, j}}$ ## C++定义 ```cpp #include <bits/stdc++.h> using namespace std; struct matrix { private: int **a; // 二维数组指针 int r, c; // r * c 矩阵 public: matrix(int m, int n) { r = m; c = n; a = new int*[r]; // 动态二维数组 for (int i = 0; i < r; i++) { a[i] = new int[c]; for (int j = 0; j < c; j++) { a[i][j] = 0; } } } int& at(const int &x, const int &y) { return a[x][y]; } int& row() { return r; } int& cal() { return c; } // 重载赋值运算符 void operator=(matrix M) { r = M.row(); c = M.cal(); a = new int*[r]; for (int i = 0; i < r; i++) { a[i] = new int[c]; for (int j = 0; j < c; j++) { a[i][j] = M.at(i, j); } } } // 重载矩阵乘法 matrix operator*(matrix &M) { matrix t(r, M.cal()); for (int i = 0; i < r; i++) { for (int j = 0; j < M.cal(); j++) { int p = 0; for (int o = 0; o < c; o++) { p += a[i][o] * M.at(o, j); } t.at(i, j) = p; } } return t; } // 输出矩阵 void print() { for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { printf("%d ", a[i][j]); } printf("\n"); } } }; // 矩阵快速幂 matrix quickpow(matrix mat, int n) { matrix base = mat, ans = mat; --n; while (n) { if (n & 1) { ans = ans * base; --n; } base = base * base; n >>= 1; } return ans; } ``` ## 用途 ### 加速递推 比如Fibonacci的递推就可以用这个加速。 #### Fibonacci第n项 定义$f(n)$为$Fibonacci$数列的第$n$项。 则$f(n) = f(n - 1) + f(n - 2)$ $f(1) = 1, f(2) =1$ 可推出 $f(n) = 1 * f(n - 1) + 1 * f(n - 2)$ $f(n - 1) = 1 * f(n - 1) + 0 * f(n - 2)$ 由矩阵的定义可得到 $\begin{bmatrix}f(n)\\f(n - 1)\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix} * \begin{bmatrix}f(n - 1)\\f(n - 2)\end{bmatrix} \Rightarrow \begin{bmatrix}f(n)\\f(n - 1)\end{bmatrix} = {\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n - 2} * \begin{bmatrix} f(2) \\f(1)\end{bmatrix}$ 然后就可以用矩阵快速幂愉快地加速啦\^_\^ #### Fibbonacci前n项和 定义$f(n)$为$Fibonacci$数列的第$n$项。 则$f(n) = f(n - 1) + f(n - 2)$ $f(1) = 1, f(2) =1$ 定义$S(n)$为$Fibonacci$数列前$n$项之和。 则$S(n) = f(1) + f(2) + \cdots + f(n) = S(n - 1) + f(n)$ 可推得 $S(n) = S(n - 1) + f(n) = 1 * S(n - 1) + 1 * f(n - 1) + 1 * f(n - 2)$ $f(n) = 0 * S(n - 1) + 1 * f(n - 1) + 1 * f(n - 2)$ $f(n - 1) = 0 * S(n - 1) + 1 * f(n - 1) + 0 * f(n - 2)$ 由矩阵定义可得 $\begin{bmatrix} S(n) \\ f(n) \\ f(n - 1) \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix} * \begin{bmatrix} S(n - 1) \\ f(n - 1) \\ f(n - 2) \end{bmatrix} \Rightarrow \begin{bmatrix} S(n) \\ f(n) \\ f(n - 1) \end{bmatrix} = {\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{bmatrix}}^{n - 2} * \begin{bmatrix} f(1) \\ f(2) \\ f(1) \end{bmatrix}$ ### 其他 待补充~~我还不会~~ 最后修改：2020 年 12 月 31 日 09 : 28 PM © 允许规范转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 支付宝支付 微信支付
