拉格朗日插值 考虑对于一个多项式 。给出 上 个点 ，它们唯一确定一个 次多项式。 考虑构造多项式 ，定义域为 ，使得当且仅当 时，，其余情况下 。假设我们找到了这样的 ， 显然就是 。 考虑这样一个函数： 它便符合上述条件。那么，我们就可以得到： 自然数幂和 求形如 的值。 首先，证明上述 是一个关于 的 次多项式。 我们求一次差分，即...

FFT 功能 快速傅里叶变换， 时间复杂度快速完成点值表达式和系数表达式的转换。一般搭配生成函数等等食用。 由于点值表达式相乘大大快于多项式卷积，所以先将多项式通过 转化为点值表达式，对应点（单位根处的值）相乘后使用 转化回多项式的形式。 基本公式 其中 是一个 次多项式， 和 分别是 取出偶次项和奇次项形成的多项式。具体过程： 所以： 至此推导完毕...

反演 https://vfleaking.blog.uoj.ac/slide/87#/炫酷反演魔术ICPC WC 2014 Day 7 以上是神级学习资料。 反演的本质 本质上来说，反演的时候我们一般会遇到形如下面式子的形式： 其中 是我们希望求得的答案， 容易直接计算得出， 是系数。一般来说，我们可能会看到形如这样的描述：设 表示恰好拥有 个属性的方案数， 为不超...

KMP 可爱的初级字符串算法。是某钻石教练会讲的算法。复杂度线性。 前缀数组（nxt） 定义： 代表 子串 最长的相等的真前缀与真后缀的长度（字符串下标从 开始）。规定 。 可以这样理解： 的意思是将字符串整体向右挪动，当 到达 的位置时，第一次出现前缀与原位置完全吻合。这样，当 位失配时，我们只需要将 挪到 的位置，保证前 位都是正确的，更改第 位。 可...