拉格朗日插值
-
拉格朗日插值法
给你 (n) 个坐标 (P(x_i,y_i))，求经过这 (n) 个点的不超过 (n-1) 次的多项式 (f(x)) 在 (k) 处的点值。
我们构造出 (n) 个多项式 (g_i(x))：
[g_i(x)=y_i imesprodlimits_{j eq i} frac{x-x_j}{x_i-x_j} ]仔细观察可以发现，(g_i(x)) 这个多项式在 (x_i) 处点值为 (y_i) ，在 (x_j(j!=i)) 处的点值全部为 (0)。这也正是我们构造它的用意。我们令:
[egin{aligned} f(x)&=sumlimits_{i=1}^n g_i(x)\ &=sumlimits_{i=1}^n y_i imes prodlimits_{j eq i} frac{x-x_j}{x_i-x_j} end{aligned} ]根据 (g_i(x)) 的定义可以发现，(f(x)) 正是我们要求的多项式。直接把 (k) 往多项式里带就好了，记得预先线性求逆元。时间复杂度：(O(n^2))。
-
在 (x_i) 连续时的做法
把上面的式子带进去：
[f(k)=sumlimits_{i=1}^{n}y_i imes prodlimits_{j eq i}frac{k-j}{i-j} ]我们记：
[pre_i=prodlimits_{j=1}^{i}k-j\ suf_i=prodlimits_{j=i}^{n}k-j\ ]那么原式就变成了这样：
[f(k)=sumlimits_{i=1}^n y_i frac{pre_{i-1} imes suf_{i+1}}{(i-1)! imes(n-j)! imes(-1)^{n-j&1}} ]这样我们就把复杂度优化到了 (O(n))。
-
重心拉格朗日插值法
记
[l(k)=prodlimits_{i=1}^n k-x_i ]那么
[egin{aligned} f(k)&=sumlimits_{i=1}^{n}y_i imes prodlimits_{j eq i}frac{k-x_j}{x_i-x_j}\ &=l(k) imessumlimits_{i=1}^n frac{y_i}{prodlimits_{j eq i}(k-x_i) imes (x_i-x_j)} end{aligned} ]然后记
[w_i=frac{y_i}{prodlimits_{j eq i} (x_i-x_j)} ]最后原式为：
[f(k)=l(k) imes sumlimits_{i=1}^n frac{w_i}{k-x_i} ]
-
-
应用
求自然数幂和：(S_k(n)=sumlimits_{i=1}^n i^k) （(nleq 10^{12} ,kleq 10^7)）
由于数据范围过大，普通的方法已经不适用，我们试着列一个式子：
[egin{aligned} S_k(n)&=sumlimits_{i=1}^{n}i^k\ &=sumlimits_{i=1}^n (i+1)^k-(n+1)^k+1\ &=sumlimits_{i=1}^n sumlimits_{j=0}^kinom k j imes i^j-(n+1)^k+1\ &=sumlimits_{i=1}^n (i^k+sumlimits_{j=0}^{k-1}inom k j imes i^j)-(n+1)^k+1\ &=S_k(n)+sumlimits_{i=1}^n sumlimits_{j=0}^{k-1}inom k j imes i^j-(n+1)^k+1 end{aligned} ]经过一波神奇的操作，我们发现 (S_k(n)) 被消掉了！这看似是一个很不好的消息，但是通过剩下来的式子我们惊喜的发现可以推出 (S_{k-1}(n)) 的表达式：
[egin{aligned} S_{k-1}(n)&=frac{-sumlimits_{i=1}^n sumlimits_{j=0}^{k-2}inom k j imes i^j +(n+1)^k -1}{k}\ &=frac{-sumlimits_{j=0}^{k-2}inom k j imes S_j(n)+(n+1)^k-1}{k} end{aligned} ]用归纳法可以很轻松的知道 (S_{k-1}(n)) 是个 (k) 次多项式。同理 (S_k(n)) 是个 (k+1) 次多项式。那么我们求 (S_k(n)) 的时候，就可以线性筛预处理出 (S_k(1),S_k(2),cdots,S_k(k+2)) 的值，然后拉格朗日插值就可以做到 (O(k)) 的时间内求出自然数幂和了。
-
例题：
快速沃尔什变换（FWT）
这篇文章里有非常详细的具体推式子过程。
-
同或运算
补充一下同或运算的式子（来自OI Wiki）：
[A_i=sumlimits_{C_1}A_j-sumlimits_{C_2}A_j ]（(C_1) 表示 (i|j) 奇偶性为 (0)，(C_2) 表示 (i|j) 的奇偶性为 (1)）
[FWT[A]=merge(FWT[A_1]-FWT[A_0],FWT[A_1]+FWT[A_0])\ IFWT[A']=merge(frac{FWT[A_1']-FWT[A_0']}{2},frac{FWT[A_1']+FWT[A_0']}{2}) ] -
例题：