当前位置：首页 > news >正文

数学相关学习笔记

news 2025/8/4 6:45:45

数学相关学习笔记

计划

2025年7月：

完善相关算法部分。

2025年8、9月：

加入”组合数学理论“部分。

2025年10月：

加入“组合数学题单和题解单”部分

线性代数理论

参考资料：自为风月马前卒的文章

可以观看视频：线性代数的本质

向量

（物理学上）向量是空间中的箭头；

（信息学上）向量是一个数列，例如 $ \begin{bmatrix} 1 \ 2 \end{bmatrix} $。

向量的基本运算有向量加减和数乘，例如

\[\begin{bmatrix} 1 \\ 2\end{bmatrix} + \begin{bmatrix} 4 \\ 3\end{bmatrix} = \begin{bmatrix} 5 \\ 5\end{bmatrix} \]

和

\[2 \times \begin{bmatrix} 4 \\ 3\end{bmatrix} = \begin{bmatrix} 8 \\ 6\end{bmatrix} \]

特殊的向量有：$\hat{i} ，\hat{j}，\hat{k}$ ，这些是平面\空间直角坐标系的基向量。

线性组合，张成，线性相关，线性无关

形如 $a\vec{u}+b\vec{v}$ 的式子叫做 $\vec{u},\vec{v}$ 的线性组合。

所有可以被给定向量线性组合的向量集合，被称为给定向量张成的空间

当你有多个向量时：

当你可以移除其中一个并不减小这些向量张成空间的维度时，我们称它们是线性相关的。
当你移除任意一个向量都会使这些向量张成空间的维度减小时，我们称它们是线性无关的。

有些时候线性无关会被表示为 $a\vec{u}+b\vec{v} = 0 (a,b\text{不全为}0)$

矩阵、线性变换

线性的定义：

（非严格）变换后所有直线都还是直线（保持网格线平行且等距分布）且原点不变。

（严格）若一个变换 $L$ 具有如下性质：$L(\vec{u})+L(\vec{v})=L(\vec{u}+\vec{v}),cL(\vec{u})=L(c\vec{u})$（分别是可加性和一阶齐次），那么 $L$ 是线性的。

矩阵的几何意义是线性变换。

矩阵乘法和复合变换

矩阵乘法的本质就是两个连续线性变换构成复合变换。

那么矩阵乘法具有结合律却不具有交换律就显而易见了。

行列式

线性变换改变面积的比例被称为这个变换的行列式

当 $det(M) < 0$ 时，$M$ 变换后空间定向改变。

当 $det(M) = 0$ 时，$M$ 变换后空间被压缩至更低维度。

性质： $det(MN)=det(M)+det(N)$

矩阵、逆矩阵和一次多元方程组

一次多元方程组一定可以被表示为： $A\vec{x}=\vec{v}$ ，其中 $A$ 是系数矩阵。

逆矩阵：若存在 $A$ 满足 $det(A) \neq 0$，那么我们称满足 $A^{-1}A=I$ 的 $A^{-1}$ 为 $A$ 的逆矩阵。

秩、列空间和零空间

秩：变换后空间的维数。

当秩和矩阵列数相等时，我们称该矩阵是满秩的。

对于变换 $A$，所有可能输出向量 $A\vec{v}$ 构成的集合叫 $A$ 的列空间。

对于变换 $A$，变换后一些向量落在零向量上，这些向量构成的空间叫 $A$ 的零空间。

点积

（代数上）对于两个同维向量，其点积为相同坐标乘积之和。

（几何上）一个向量在另一个向量所在直线的正交投影的长度和另一个向量长度的乘积。

这两者是可以互相转化的，理解通过对偶性，详见视频。

叉积

叉积是三维空间中两个向量的二元运算,记作 $\vec{u} \times \vec{v}$

对于 $\vec{u} \times \vec{v} = \vec{w}$，$\vec{w}$ 满足大小为 $\det(\vec{v},\vec{u} \text{列构成的矩阵})$，方向垂直于 $\vec{v}，\vec{u}$ 且满足右手定则（可以让食指指向 $\vec{u}$，中指指向 $\vec{v}$ ，拇指指向 $\vec{w}$）

特征向量和特征值

特征向量和特征值都是相对于一个变换 $M$ 而言的。

如果一个向量 $\vec{u}$ 在变换后仍处于它张成空间，那么 $\vec{u}$ 是 $M$ 的特征向量。

对于一个特征向量 $\vec{u}$ ，它在变换后的长度和变换前的长度之比叫它的特征值。

相关算法

高斯消元

参考资料：ShineEternal的文章

这里只讲高斯-约旦消元。

主要思想是：把系数矩阵 $A$ 通过线性变换变换为一个对角矩阵。

具体操作：

找到第 $1$ 列的元素最大的行，并把其和第 $1$ 行交换；
把第 $1$ 行第 $1$ 列的元素通过线性变换变成 $1$；
其他行通过减去若干倍的第 $1$ 行使自己这一行的第 $1$ 列的元素变为 $0$；
依次对其他行重复操作；

特殊情况：

如果存在消元后左边系数为 $0$ 而右边系数不为 $0$ 情况（例如 $0*x_i=y$），那么该方程无解。
如果存在消元后左边系数为 $0$ 而右边系数为 $0$ 情况（例如 $0*x_i=0$），那么该方程有无穷解；但是在实际解题构造方案时，可以把当前行的解看作 $x_i=0$ 来简化操作。

应用：

矩阵求逆：因为 $A$ 通过高斯消元变成了 $I$，等价于乘上 $A^{-1}$。那么我们只需要对 $A$ 进行高斯消元，并在做线性变换时维护一个初始为 $I$ 的矩阵 $B$，对 $B$ 进行相同的线性变换，最后得到的 $B$ 就是 $A^{-1}$。

例题：

P3389 【模板】高斯消元法
P4783 【模板】矩阵求逆
P2455 [SDOI2006] 线性方程组

线性基

参考资料：Troverld的文章 Marser的题解

这里只讲异或线性基。

线性基是一个序列生成的集合，并且满足如下性质：

线性基中选出若干（非零）数的异或值所构成的集合，等于原序列中选出若干（非零）数的异或值所构成的集合；
线性基是满足性质 $1$ 的最小集合；
原序列中的任何数都可以由线性基中的若干数异或得到；
线性基中不存在一组数，使得它们的异或和为 $0$（反证法：如果存在这么一组数 $a_1,a_2,...,a_n$，使得 $a_1 \oplus a_2 \oplus a_3 ... \oplus a_n=0$，那么一定存在 $a_1 = a_2 \oplus a_3 ... \oplus a_n$，那么 $a_1$ 是没有用的，可以删去）；
线性基中不存在两组数，使得它们的异或和相等（证明类似）；

实现：

维护一个 $d$ 数组，$d_i$ 满足 $d_i$ 的二进制表示中，第 $i$ 位是 $1$，第 $i+1$ 位及之后都是 $0$；

插入操作：核心思想是**尽量把 $x$ 通过与 $d_i$ 异或变成 $0$ **，因此我们只需要从高位到低位判断 $x$ 当前位是否为 $1$，如果不是，就往低位判断；如果是，那么如果 $d_i$ 存在，那么 $x \leftarrow x \oplus d_i$，并向低位判断；否则就 $d_i \leftarrow x$；

时间复杂度：$O(n \log V)$，$n$ 是数组长度，$V$ 是值域大小。

支持询问：

最小异或和：因为线性基中不存在两个二进制最高位相同的数，因此答案就是线性基中最小数
最大异或和：考虑从高位到低位遍历线性基，考虑到第 $i$ 时，如果当前位为 $1$，那么向低位遍历；否则就异或 $d_i$ ，因为这么做不会使答案更劣。
第 $k$ 小异或和：考虑简化 $d_i$ 的贡献，如果 $d_i$ 的 $j(j <i)$ 位为 $1$ 且 $d_j$ 存在，那么 $d_i$ 的第 $j$ 位的贡献一定也可以被 $d_j$ 处理，那么可以 $d_i \leftarrow d_i \oplus d_j$ ，这么操作是可以在原线性基上做的，因为异或操作是可抵消的，上述操作可以在 $O(\log^2n)$ 的时间内处理。处理询问时，先进行因此简化，在对 $k$ 进行二进制拆分：如果 $k$ 的第 $i$ 位是 $1$，那么就 $ans \leftarrow ans \oplus d_j$，其中 $d_j$ 是 $d$ 数组从后往前第 $i$ 个有值的数。