数学部分2025.6.24

· · 个人记录

代数学

通过理论推导，得出一些抽象得代数性质，遇到具象的集合或其他得东西，就有这样得结论

代数结构

OI中常用得有半群，群，环，域。

半群：满足结合律的一个集合。 可以用线段树和快速幂

群：满足结合律和运算可逆，并存在一个单位元，即 \forall a \in S \ \exists e \ \ s.t. \ ae=ea=a ，同时满足 \forall a \in S \ \exists \ a^{-1} \ s.t. \ aa^{-1} =a^{-1}a = e （就是运算可逆） 可用树状数组来维护（具有信息可减性）

域：定义了满足结合律、可逆的加法，满足结合律、分配律、可逆的乘法，注意这里的乘法与加法不是常规意义下的加法和乘法，而是一种类似于函数的映射。可以像 R 域一样进行四则运算

线性代数

代数：若干个变元（未知数） x_1,x_2,...,x_n

线性：只有一次项（一般认为没有零次项）

把一列数组合在一起，就是一个向量 (x_1,...,x_n)^T

一个向量变成另一个向量，就是变换。

如果变换后的新向量与原来的向量都是线性，则这个变换是线性变换

矩阵

我们有两种定义矩阵的方法，第一种是我们把一个 n 维的向量中的每一个数替换为一个 m 维的向量，这样我们就得到了一个 n \times m 的矩阵。 第二种定义是矩阵描述了一个线性变换，将向量与矩阵做乘法，得到另一个向量，这就是一个线性变换。

矩阵乘法

本质上是一种线性变换，运算规则为

C(i,j) = \sum_k A(i,k)*B(k,j)

矩阵乘法具有结合律，也就可以看作是线性变换的复合（这里的复合与函数的复合的定义一样，就是 f(x) 与 g(x) 的复合是 f(g(x)) ）

矩阵乘法通常不具有交换律，要特别注意写代码时的顺序问题

矩阵快速幂

这个可以解决递推问题，将要递推的视作一个向量，递推完后的东西视作另一个向量，凑出中间的转移矩阵，后就可以矩阵快速幂快速计算。

要注意的是当转移时有常数项形如 n^k 时，要在这一维的向量中塞 n^0 到 n^k , 在下一步中塞 0 到 (n+1)^k ,这样就可以二项式定理（ (a+b)^n = \sum_{i=0}^{n} a^i b^{(n-i)} \binom{n}{i} ）展开,将组合数放在转移矩阵中，就可以进行转移了。

初等变换

见ppt

行列式

略

线性相关与线性无关

线性组合与线性空间

线性空间的基

矩阵的秩

矩阵的逆与方程的解

不可逆矩阵与方程的解

见ppt

下午，见ppt 重要公式