拉格朗日插值法 小结

拉格朗日插值法是干啥的

用来合理的解释你按规律填数乱填的答案

给定n个点$(x_i,y_i)$，求一个n-1次多项式经过这n个点。

算法流程

考虑把这个多项式$f(x)$拆成n个多项式$f_i(x)$，使得第i个多项式在$j=i$时，$f_i(x_j)=1$，并且在$j\not= i $时，$f_i(x_j)=0$。那么$f(x)=\sum y_if_i(x)$

首先由于$j\not=i$时$f_i(x_j)=0$，那么$f_i(x)$有一个$(x-x_j)$因子。设$f_i(x)=\prod\limits_{j\not =i}(x-x_j)s$

由于$j=i$时$f_i(x_j)=1$，那么$s=\frac{1}{\prod\limits_{j\not =i}(x_i-x_j)}$。

也就是说，$f_i(x)=\prod\limits_{j\not=i}\frac{x-x_j}{x_i-x_j}$，$f(x)=\sum\limits_i (y_i\prod\limits_{j\not=i}\frac{x-x_j}{x_i-x_j})$。

这个显然是n-1次的。

实现

如果你需要插出一个x位置的值，很方便做到$O(n^2)$，如果需要插出这个多项式？

$\prod\limits_{j\not =i} (x-x_j)$ 不是要$O(n^2)$乘？

可以先$O(n^2)$算出$g(x)=\prod (x-x_i)$，然后每次计算$\frac{g(x)}{(x-x_i)}$只要$O(n)$。还是$O(n^2)$。

如果$x_i=i$？分母部分可以先预处理阶乘逆元，分子部分可以拆成两部分相乘，就只需要$O(n)$了。当然$f(x)$在$x\le n$要特判。插出多项式？不会。

例题

涂色

有一个长度为n的序列初始全为白色，进行k次操作，每次随机选两个点将它们之间染黑。

求期望被染黑的点数。$n\le 10^9,k\le 10^3$（其实可以$k\le 10^6$）

根据期望的线性性，可以分开算每个点被染黑的概率（答案就是每个点被染黑概率的和

第i个点染黑的概率$=1-($单次没染黑的概率$)^k$

单次没染黑的概率显然$= \frac{(i-1)^2+(n-i)^2}{n^2}$

那么答案就是$n-\frac{\sum\limits_{i=1}^n((i-1)^2+(n-i)^2)^k}{n^{2k}}$

设$f(x)=\sum\limits_{i=1}^x((i-1)^2+(n-i)^2)^k$。

这东西看上去是$2k+1$次的（x个2k次的多项式和？）

然后就可以先算x=1到2k+2的$f(x)$，然后拉格朗日插值算出$f(n)$。时间复杂度$O(k\log k)$（2k+2次计算每次需要$O(\log k)$）

CF622F

求$\sum\limits_{i=1}^ni^k$，其中$k\le 10^6,n\le 10^9$，输出对1e9+7取膜。

设这个为$f(n)$

这个看上去是一个k+1次多项式（n个k次的和？）

那就先算$f(1)..f(k+2)$，然后插值。时间复杂度$O(k\log k)$。