拉格朗日插值法 小结
拉格朗日插值法是干啥的
用来合理的解释你按规律填数乱填的答案
给定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)$。