拉格朗日插值
　　拉格朗日插值法
　　给你 (n) 个坐标 (P(x_i,y_i))，求经过这 (n) 个点的不超过 (n-1) 次的多项式 (f(x)) 在 (k) 处的点值。
　　我们构造出 (n) 个多项式 (g_i(x))：
　　[g_i(x)=y_i\times\prod\limits_{j\neq i} \frac{x-x_j}{x_i-x_j} ]
　　仔细观察可以发现，(g_i(x)) 这个多项式在 (x_i) 处点值为 (y_i) ，在 (x_j(j!=i)) 处的点值全部为 (0)。这也正是我们构造它的用意。我们令:
　　[\begin{aligned} f(x)&=\sum\limits_{i=1}^n g_i(x)&=\sum\limits_{i=1}^n y_i\times \prod\limits_{j\neq i} \frac{x-x_j}{x_i-x_j} \end{aligned} ]
　　根据 (g_i(x)) 的定义可以发现，(f(x)) 正是我们要求的多项式。直接把 (k) 往多项式里带就好了，记得预先线性求逆元。时间复杂度：(O(n^2))。
　　在 (x_i) 连续时的做法
　　把上面的式子带进去：
　　[f(k)=\sum\limits_{i=1}^{n}y_i \times \prod\limits_{j\neq i}\frac{k-j}{i-j} ]
　　我们记：
　　[pre_i=\prod\limits_{j=1}^{{i}k-j\suf_i=\prod\limits_{j=i}}{n}k-j\]
　　那么原式就变成了这样：
　　[f(k)=\sum\limits_{i=1}^n y_i \frac{pre_{i-1}\times suf_{i+1}}{(i-1)!\times(n-j)!\times(-1)^{n-j&1}} ]
　　这样我们就把复杂度优化到了 (O(n))。
　　重心拉格朗日插值法
　　记
　　[l(k)=\prod\limits_{i=1}^n k-x_i ]
　　那么
　　[\begin{aligned} f(k)&=\sum\limits_{i=1}^{n}y_i \times \prod\limits_{j\neq i}\frac{k-x_j}{x_i-x_j}&=l(k)\times\sum\limits_{i=1}^n \frac{y_i}{\prod\limits_{j\neq i}(k-x_i)\times (x_i-x_j)} \end{aligned} ]
　　然后记
　　[w_i=\frac{y_i}{\prod\limits_{j\neq i} (x_i-x_j)} ]
　　最后原式为：
　　[f(k)=l(k)\times \sum\limits_{i=1}^n \frac{w_i}{k-x_i} ]
　　应用
　　求自然数幂和：(S_k(n)=\sum\limits_{i=1}^n i^k) （(n\leq 10^{12} ,k\leq 10^7)）
　　由于数据范围过大，普通的方法已经不适用，我们试着列一个式子：
　　[\begin{aligned} S_k(n)&=\sum\limits_{i=1}^{n}ik&=\sum\limits_{i=1}^n (i+1)^k-(n+1)k+1&=\sum\limits_{i=1}^n \sum\limits_{j=0}^k\binom k j \times i^j-(n+1)k+1&=\sum\limits_{i=1}^n (i^{k+\sum\limits_{j=0}}{k-1}\binom k j \times i^j)-(n+1)k+1&=S_k(n)+\sum\limits_{i=1}^n \sum\limits_{j=0}^{k-1}\binom k j\times i^j-(n+1)k+1 \end{aligned} ]
　　经过一波神奇的操作，我们发现 (S_k(n)) 被消掉了！这看似是一个很不好的消息，但是通过剩下来的式子我们惊喜的发现可以推出 (S_{k-1}(n)) 的表达式：
　　[\begin{aligned} S_{k-1}(n)&=\frac{\sum\limits_{i=1}^n \sum\limits_{j=0}^{k-2}\binom k j \times i^j -(n+1)^k +1}{k}&=\frac{\sum\limits_{j=0}^{k-2}\binom k j\times 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+1)) 的值，然后拉格朗日插值就可以做到 (O(k)) 的时间内求出自然数幂和了。
　　例题：
　　luogu P4781 【模板】拉格朗日插值 题解
　　luogu P4593 [TJOI2018]教科书般的* 题解
　　快速沃尔什变换（FWT）
　　这篇文章里有非常详细的具体推式子过程。
　　同或运算
　　补充一下同或运算的式子（来自OI Wiki）：
　　[A_i=\sum\limits_{C_1}A_j-\sum\limits_{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}) ]