数学部分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$ 的矩阵。 第二种定义是矩阵描述了一个线性变换，将向量与矩阵做乘法，得到另一个向量，这就是一个线性变换。

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

矩阵乘法具有结合律，也就可以看作是线性变换的复合（这里的复合与函数的复合的定义一样，就是 $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 重要公式