Login to join training plan

矩阵基础

https://oi-wiki.org/math/linear-algebra/matrix/

通俗理解，矩阵就是一个二维数组。例如：$A = \begin{bmatrix} A_{1, 1} & A_{1, 2} & \dots & A_{1, m}\\ A_{2, 1} & A_{2, 2} & \dots & A_{2, m}\\ \vdots & \vdots & \ddots & \vdots\\ A_{n, 1} & A_{n, 2} & \dots & A_{n, m}\end{bmatrix}$

矩阵信息：

• 行数，列数；
• 每行每列的元素；
• 秩，行列式；

名称

主对角线：$A_{i, i}$ 的元素；

方阵：行列数都为 $n$ 的矩阵叫做方阵。

上三角矩阵：以 $(1, 1)$ 到 $(n, n)$ 的对角线为界，左下全都是 $0$ 的矩阵。

---

初等行列变换

https://oi-wiki.org/math/linear-algebra/elementary-operations/#%E5%88%9D%E7%AD%89%E5%8F%98%E6%8D%A2

初等行列变换：

• 交换任意两行或两列；
• 某一行增加 $k$ 倍的另一行 或 某一列增加 $k$ 倍的另一列；
• 某一行扩大 $k$ 倍 或 某一列扩大 $k$ 倍；

初等行列变换的形式简单，但性质不变。

---

高斯消元

https://oi-wiki.org/math/linear-algebra/gauss/

利用矩阵初等行列变换将方阵消成上三角矩阵。

操作：

• 用第一行乘以相应的系数消掉 $[2, n]$ 行的第一列；
• 用第二行乘以相应的系数消掉 $[3, n]$ 行的第二列；
• ......
• 用第 $k$ 行乘以相应的系数消掉 $(k, n$] 行的第 $k$ 列；

本质上就是个加减消元法。

高斯消元的应用：

• 解多元一次方程；
• 求矩阵的秩；
• 求矩阵的行列式；

时间复杂度 $\Theta(n ^ 3)$。

---

矩阵乘法

https://oi-wiki.org/math/linear-algebra/matrix/#%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95

有结合律，没有交换律。

$A \times B = C$，那么结果有如下规律：

$C$ 的行数是 $A$ 的行数，$C$ 的列数是 $B$ 的列数。

$A$ 的列数和 $B$ 的行数应当相等，假设为 $k$。

$C_{i, j}$ 是 $A$ 的第 $i$ 行和 $B$ 的第 $j$ 列按位相乘再加和的结果，即 $C_{i, j} = A_{i, 1}\times B_{1, j} + A_{i, 2}\times B_{2, j} + \dots + A_{i, k}\times B_{k, j}$。

矩阵求逆

https://oi-wiki.org/math/linear-algebra/matrix/#%E6%96%B9%E9%98%B5%E7%9A%84%E9%80%86

假设矩阵 $A$ 的逆矩阵 $B$，那么可以得到：

$A \times B = I$。

$I$ 是除了主对角线是 $1$，其余都为 $0$ 的矩阵。即 $I = \begin{bmatrix}1 & 0 & 0 & 0\\0 & 1 & 0 & 0\\0 & 0 & \ddots & 0\\0 & 0 & 0 & 1\end{bmatrix}$。

将 $A$ 和 $I$ 拼在一起，将 $A$ 高斯消元消成 $I$，右面的 $I$ 跟着做同样的初等行列变换，这样 $I$ 最后的结果就变成了 $B$。

---

矩阵快速幂

把快速幂原理应用到矩阵上就可以求 $A^k$。

快速幂函数不变，把整型变成矩阵型 (struct) 即可。

注意重载矩阵乘法运算符。

时间复杂度 $\Theta(n^3 \log k)$。

优化递推（DP）

https://oi-wiki.org/math/linear-algebra/matrix/#%E7%9F%A9%E9%98%B5%E5%8A%A0%E9%80%9F%E9%80%92%E6%8E%A8

如果要快速求 $f_i$ 的值，其中 $f$ 表示斐波那契数列，那么可以用矩阵快速幂的方法。

由于 $f_i = f_{i - 1} + f_{i - 2}$，所以可以通过下面的方法求解 $f_i$。

定义两个 $2 \times 2$ 的矩阵 $F$ 和 $M$。其中 $M = \begin{bmatrix}0 & 1\\1 & 1\\\end{bmatrix}$，$F$ 初始为 $\begin{bmatrix}f_1 & f_2\\0 & 0\\\end{bmatrix}$。

将 $F$ 更新成 $F$ 与 $M$ 的乘积，即 $F = \begin{bmatrix}f_1 \times 0 + f_2 \times 1 & f_1 \times 1 + f_2 \times 1\\0 \times 0 + 0 \times 1 & 0 \times 1 + 0 \times 1\\\end{bmatrix} = \begin{bmatrix}f_2 & f_3\\0 & 0\\\end{bmatrix}$，那么此时我们就得到了 $f_3$ 的值。

同理，如果再次 $F \leftarrow F \times M$，我们也可以得到 $f_4$ 的值。那么如果要得到 $f_n$ 的值只需要计算 $F \times M^{n - 2}$ 即可，那么最后就有 $f_n = F_{1, 2}$。

这样我们就把求斐波那契数列的 $\Theta(n)$ 的复杂度降到了 $\Theta(\log n)$，是十分优秀的。

这样我们就把一个递推问题通过矩阵快速幂的形式进行了优化，同理对于一些其它的递推式也是可以通过类似的方法优化。

---

数学性质

• 在 $\bmod$ 质数意义下 $1 \sim n - 1$ 逆元互不相同。

• $n = \sum\limits_{d \mid n} \varphi(d)$

• 两个不同数的 $\gcd$ 不会超过两个数的差。

• $\gcd(a, b) = 1 \Longleftrightarrow \gcd(a + k \times b, b) = 1$

• $C_n^k = C_{n-1}^{k-1} \times \dfrac nk$

• $n$ 个 $[0, 1]$ 随机变量的期望 $k$ 小是 $\dfrac k{n + 1}$。

• 在 $\gcd(a_1, a_2, a_3, \dots, a_n)$ 中，$\forall i \ne j,a\pm a_j$ 都不会对答案产生影响。

• $\sum\limits_{i = 0}^k C_{n + r - 1}^r = C_{n + k}^k$

• $C_n^m = \prod\limits_{i = 1}^m\dfrac{n+1-i}i$

• 卡特兰数：

  • $h_0 = h_1 = 1$
  • $h_n = \sum\limits_{i = 0}^{n - 1}h_i \times h_{n - i - 1} = \dfrac{C_{2n}^n}{n + 1}$

• $\left\lceil \dfrac AB \right\rceil = \left\lfloor \dfrac{A+B-1}B \right\rfloor$