OI | Limstash的博客

[学习笔记] 生成函数基础

生成函数是解决组合问题的一个重要工具，本文介绍了普通生成函数 $\mathrm{OGF}$ 和指数生成函数 $\mathrm{EGF}$ 的相关推导

题目背景对于一棵树，我们定义 $dis(i, j)$ 为节点 $i$ 和 $j […]

杜教筛是一个可以在 $O(n^{\frac{2}{3}})$ 的时间内计算积性函数前缀和的一种筛法

题目描述给定 $N$ 和 $M$，求 $1 \leq x \leq N$，$1 […]

题目描述废话不多说，反正小w要发喜糖啦！！小w一共买了 $n$ 块喜糖，发给 […]

$\mathrm{FHQ} \ \mathrm{Treap}$ 是一类基于 $\mathrm{Split}$ 和 $\mathrm{Merge}$ 操作的平衡树，不需要旋转的特性是可持久化平衡树的基础

多项式操作包括多项式求逆，多项式 $\ln$，多项式 $\mathrm{exp}$，多项式开根，多项式取模等，是在生成函数中常用的多项式操作

Kruskal 重构树是一种基于 Kruskal 算法，在求解最小生成树的同时建出一棵新树。Kruskal 重构树是一个二叉堆，原图两点之间边权最大值等于 Kruskal 重构树上 LCA 权值

整除分块（数论分块）是一类在莫比乌斯反演等数学题中常用到的一个求和技巧

替罪羊树（重量平衡树）和 Treap （树堆）也是两种常用的平衡树，分别基于平衡因子和随机附加域来保证子树的平衡。