网络——http常见状态码
2021-01-14 01:13
-
拉格朗日插值法
给你 \(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}i^k\&=\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]教科书般的亵渎 题解