拉格朗日插值法 小结

拉格朗日插值法是干啥的

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

给定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)$。

# 数学

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×