多项式 - 生成函数
生成函数是用来描述一个有穷或无穷序列的工具,我们只关心它的系数而不关心自变量的具体取值,在一系列计数问题中有很大的作用。
字符串 - Manacher
Manacher 可以在 O(n) 的复杂度内求解所有位置的最长回文串。
多项式 - 初等函数
基于 FFT 可以 O(nlog(n)) 的计算多项式卷积,可以推出一系列多项式的初等函数,本文记录一些不全面初等函数及模板,包括多项式乘法、乘法逆、除法、开根、取模、对数、指数。
数学 - 单位根反演
单位根反演是 FFT 的基础,并且它也可以解决一些其它的问题。
多项式 - 常系数齐次线性递推
对于一个线性递推,利用多项式取模可以做到比矩阵优秀很多的复杂度,当然也比较难写。
数学 - 拉格朗日插值法
用 n+1 个点可以唯一确定一个 n 次多项式,拉格朗日插值法给出一个构造此多项式的方法。
数学 - 幂平均不等式
幂平均不等式是常见的均值不等式的拓展,本文利用 Jensen 不等式来证明幂平均不等式。
图论 - 动态修改非负边权树的直径问题
用线段树维护欧拉序可以做到 O(nlog(n)) 复杂度动态带修改非负边权的求出一个树的直径。若边权存在负数,应当使用动态 DP 等方法解决。
数学 - Jensen 不等式
Jensen 不等式阐明均值的函数值与函数值的均值之间的不等关系,本文用数学归纳法结合凸函数的性质来进行证明并阐述取等条件。
数学 - 超几何分布的期望和方差
由于用自己没推导过的公式心里没有底,所以写篇博客记录一下推导超几何分布的期望和方差的过程。