拉格朗日插值法 小结

拉格朗日插值法是干啥的

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

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

算法流程

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

首先由于 fi(xj)=0f_i(x_j)=0,那么fi(x)f_i(x)有一个(xxj)(x-x_j)因子。设

由于j=ij=ifi(xj)=1f_i(x_j)=1,那么

也就是说,

这个显然是n-1次的。

实现

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

不是要O(n2)O(n^2)乘?

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

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

例题

涂色

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

求期望被染黑的点数。n109,k103n\le 10^9,k\le 10^3(其实可以k106k\le 10^6

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

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

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

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

f(x)=i=1x((i1)2+(ni)2)kf(x)=\sum\limits_{i=1}^x((i-1)^2+(n-i)^2)^k

这东西看上去是2k+12k+1次的(x个2k次的多项式和?)

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

CF622F

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

设这个为f(n)f(n)

这个看上去是一个k+1次多项式(n个k次的和?)

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

文章目录
  1. 1. 拉格朗日插值法是干啥的
  2. 2. 算法流程
  3. 3. 实现
  4. 4. 例题
    1. 4.1. 涂色
    2. 4.2. CF622F
|

博客使用Disqus作为评论系统