四月 23, 2024
后缀数组 & 后缀自动机
后缀数组（SA）定义给定一个字符串 $S{1 \dots n}$，你需要对这个字符串的 $n$ 个后缀按照字典序排序，排序后的下标数组就是 $sa_i$，...
四月 03, 2024
拉格朗日插值 & 线性递推
拉格朗日插值动态拉格朗日插值插值公式（$n$ 个点 $x_i,y_i$ 确定一个 $n-1$ 次多项式，求出点 $x$ 处的取值）： $$f(x) &#x...
四月 03, 2024
快速沃尔什变换 FWT/子集卷积
快速沃尔什变换 FWT给定两个数组 $A,B$，求出 $A,B$ 经过下列变换之后得到的 $C$ 数组，快速计算。 $$C_i = \sum_{...
三月 10, 2024
数学学习笔记7
多项式备注：多项式基本操作此处不再说明，都比较简略，此处只介绍重要结论以及算法。 Warning：这篇文章有的公式是无法显示的，建议在洛谷 “多项式科技”...
二月 18, 2024
KTT & Segment Tree Beats
KTT & 吉司机线段树首先，吉司机线段树是一种用来维护区间取 $\max$，区间求和的操作，它的时间复杂度是通过势能分析得到的 $O(n \lo...
二月 10, 2024
K-D Tree
K-D TreeK-D 树存储了 $K$ 维空间下 $n$ 个点的信息，我们可以在树上执行若干操作和若干查询，下面记录了一些常见的用法。 构建首先给出 K...