矩阵 是一种用于简化运算的工具，很神奇的。
（未完待续）
矩阵的定义
矩阵其实就是一对数字的有机组合，是一种方便我们简化计算的工具（尽管矩阵的形式并不是很简便）。
矩阵运算
矩阵加法
只有行数和列数都相等的矩阵才能相加，矩阵的加法运算法则用公式表示为：
$$\text{C} _ {i,j}=\text{A} _ {i,j}+\text{B} _ {i,j}$$
值得注意的是，矩阵加法运算的单位元是一个各项都为零的矩阵。
矩阵乘法
对于一个 $n$ 行 $m$ 列的矩阵 $\text{A}$ 与一个 $m$ 行 $k$ 列的矩阵 $\text{B}$，他们的乘积为一个 $n$ 行 $k$ 列的矩阵 $\text{C}$，具体地，我们有：
$$\text{C} _ {i,j}=\sum^m _ {k=1}\text{A} _ {i,k} \text{B} _ {k,j}$$
当然，在矩阵乘法中，结果 $\text{C}$ 矩阵的第 $i$ 行第 $j$ 列的数，就是由矩阵 $\text{A}$ 第 $i$ 行 $k$ 个数与矩阵 $\text{B}$ 第 $j$ 列 $k$ 个数分别相乘再相加得到的。
性质
单位元
矩阵乘法的单位元是一条从左上到右下角的 $1$，例如 $3\times 3$ 的矩阵的乘法单位元是：
$$
\begin{bmatrix}
1&0&0\\
0&1&0\\
0&0&1
\end{bmatrix}
$$
结合律
矩阵乘法符合结合律，下面是证明。
证明略。
应用
因为矩阵乘法符合结合律，我们往往把一个矩阵视作一种操作。
首先对于比较小的矩阵，可以考虑直接手动展开循环以减小常数。
可以重新排列循环以提高空间局部性，这样的优化不会改变矩阵乘法的时间复杂度，但是会在得到常数级别的提升。这与内存的缓存机制有关。
- 慢
inline Matrix operator*(const mat& T) const {
mat res;
for (int i = 0; i < sz; ++i)
for (int j = 0; j < sz; ++j)
for (int k = 0; k < sz; ++k) {
res.a[i][j] += mul(a[i][k], T.a[k][j]);
res.a[i][j] %= MOD;
}
return res;
}
- 快
inline mat operator*(const mat& T) const {
mat res;
int r;
for (int i = 0; i < sz; ++i)
for (int k = 0; k < sz; ++k) {
r = a[i][k];
for (int j = 0; j < sz; ++j) res.a[i][j] += T.a[k][j] * r;
res.a[i][j] %= MOD;
}
return res;
}
广义矩阵乘法
我们往往会到一种奇怪的矩阵乘法的定义：
$$\text{C} _ {i,j}=\max^m _ {k=1} \{\text{A} _ {i,k}+\text{B} _ {k,j}\}$$
动态 $\text{DP}$ 中往往会使用这种特殊的矩阵乘法的定义。
简单应用
未完待续
近期评论