k 进制异或线性基
May 24, 2024 •
Comment
不知道 nfls 模拟赛为什么出这种抽象东西，也不知道这玩意有什么用。
dfs 序优化树上依赖性背包学习笔记
November 2, 2023 •
Comment
我们知道对于树上背包，若每个结点上只有总大小为 $O(1)$ 的物品，则总复杂度为 $O(n^2)$；若再限制背包大小为 $m$，则总复杂度为 $O(nm)$。
再谈树上背包的上下界优化
July 5, 2023 •
Comment
关于树上背包的上下界优化，当时 fz 推荐我读的是 ouuan 的文章（cnblogs github pages），但是，我现在认为那里面的复杂度证明存在问题。
Erdos-Ginzburg-Ziv Theorem
March 29, 2023 •
Comment
Erdos-Ginzburg-Ziv Theorem
对任意 $2n-1$ 个整数，可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。
形式化的，对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$，存在两两不同的 $i_1,\dots,i_n$ 使得：
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$