·

二分图博弈学习笔记

两人在一二分图上进行决策,初始状态为二分图的一个点,两人轮流沿边行动,不允许重复访问节点,无法移动者输。 这样的问题称为二分图博弈。

·

根号数据结构复习

分块,可以看做一个度数为 $\sqrt n$,只有三层的树。 所以如果在分治结构上很难快速合并某些信息,我们就可以利用分块来做。

·

五边形数定理学习笔记

五边形数生成函数即欧拉函数: $\displaystyle{ \varphi(x) = \prod_{n=1}^\infty (1 - x^n) }$

·

拟阵与拟阵交学习笔记

本文以矩阵交相关内容为主,忽略掉了大部分证明,感兴趣的读者请自行阅读集训队论文。 拟阵的定义记 $M = (S, L)$ 表示一个定义在有限集 $S$ 上,独立集的集合为 $L$ 的拟阵。其中 $L$ 是 $S$ 的一些子集构成的集合。拟阵 $M$ 满足以下公理: (遗传性). 如果 $I \in L, J \subseteq I$,那么 $J \in L$。 (交换性). 如果 $I,J \in L$ 且 $|I| < |J|$,...

·

动态线性基学习笔记

前置知识:维护线性基本质上维护了一个向量空间,或者说是一个以基底为元素的集合。 例题维护一个集合,支持修改某数的权值,求最大异或值。

·

多项式多点求值与快速插值学习笔记

多点求值我们若求一个一次函数 $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}$ ~ $x_r$ 的多项式,对 ...