拉格朗日插值 & 自然数幂和

拉格朗日插值

考虑对于一个多项式。给出上个点，它们唯一确定一个次多项式。

考虑构造多项式，定义域为，使得当且仅当时，，其余情况下。假设我们找到了这样的，显然就是。

考虑这样一个函数：

它便符合上述条件。那么，我们就可以得到：

求形如

的值。

首先，证明上述是一个关于的次多项式。

我们求一次差分，即记，那么我们有

而这是一个关于的次多项式。又因为差分会降低一次，所以原式是一个关于的次多项式。

然后拉插即可。

考虑一种特殊的拉插，当我们可以自由选择插入的值时（以上述自然数幂和为例），我们将带入，这种情况下上述拉插过程的复杂度可以降低到。

具体来说，我们将上式变形：

考虑处理出的前缀积和后缀积，再处理出阶乘逆元，就可以求出答案。

对于上面的式子：

首先提取常数部分，设，这个可以简单地求出。

之后，式子化为：

接下来考虑一个辅助多项式，可以逐次加入，递推得出的系数。上述式子可以化为：

再设。我们有。接下来提取系数：

递推即可得到的系数，累加得到的系数。复杂度。