十二月 26, 2019 · OI 算法
五边形数定理学习笔记
五边形数生成函数即欧拉函数： $\displaystyle{ \varphi(x) = \prod_{n=1}^\infty (1 - x^n) }$
九月 27, 2019 · OI 算法
拟阵与拟阵交学习笔记
本文以矩阵交相关内容为主，忽略掉了大部分证明，感兴趣的读者请自行阅读集训队论文。 拟阵的定义记 $M = (S, L)$ 表示一个定义在有限集 $S$ 上，独立集的集合为 $L$ 的拟阵。其中 $L$ 是 $S$ 的一些子集构成的集合。拟阵 $M$ 满足以下公理： (遗传性). 如果 $I \in L, J \subseteq I$，那么 $J \in L$。 (交换性). 如果 $I,J \in L$ 且...
二月 24, 2019 · OI 算法
多项式多点求值与快速插值学习笔记
多点求值我们若求一个一次函数 $f(x) = ax + b$ 在 $x_0$ 处的值，可以拿 $f(x)$ 对 $(x - x_0)$ 取模，得到的零次多项式即在 $x_0$ 处的点值，容易证明其正确性。 考虑分治，假设我们需要求 $x_l$ ~ $x_r$ 处的点值，可以通过当前的 $f(x)$ 对 $\prod_{i=l}^{mid} (x-x_i)$ 取模得到递归到 $x_{mid + 1}$ ~ ...