关于拉格朗日插值
TLE_Automat
·
·
个人记录
给定 n+1 个横坐标不同的点，求一个 n 次多项式在其他位置的取值，直接高斯消元法算多项式系数的时间复杂度是 O(n^3) 的，有没有更快的方法呢。
有，就是拉格朗插值法。
前置知识
首先由一个显然的结论，若 a 是整数，则有
x \equiv a \pmod{x-a}
根据同余的性质，若 k 是整数，则有
x^k \equiv a^k \pmod{x-a}
于是可以进一步得出结论，若 f(x) 是关于 x 的多项式，则有
f(x) \equiv f(a) \pmod{x-a}
结论推导
设给定的 n+1 个点的横坐标分别为 x_0 , x_1 ,\cdots ,x_{n} ，根据上述结论，则有同余方程组
\left\{\begin{aligned}
f(x) &\equiv f(x_0) \pmod{x-x_0} \\
f(x) &\equiv f(x_1) \pmod{x-x_1} \\
&\cdots \\
f(x) &\equiv f(x_n) \pmod{x-x_n} \\
\end{aligned}
\right.
要得到 f(x) 的表达式，实际上就是解这个同余方程组，这就很自然地让我们联想到了中国剩余定理。
设 N = \prod\limits_{i=0}^{n} (x-x_i) ，则对于第 i 个同余式的基向量就是
\boldsymbol{e_i} = \frac{N}{x-x_i} \left(\frac{N}{x-x_i}\right)^{-1}_{\bmod x-x_i} = \prod\limits_{j\neq i} \frac{x-x_j}{x_i - x_j}
所以用中国剩余定理合并起来就是
f(x) = \sum\limits_{i=0}^{n} f(x_i) \boldsymbol{e_i} = \sum\limits_{i=0}^{n} f(x_i) \prod\limits_{j\neq i} \frac{x-x_j}{x_i - x_j}
这样，我们只需要 O(n^2) 的时间复杂度便可以求出 f(x) 在其他位置的取值了，有一些题还有一些性质，可以做到 O(n\log n) 甚至 O(n) 。
一个例题
求 S_k(n) = \sum\limits_{i=0}^{n} i^k ，1\le n \le 10^9 , 1\le k \le 10^6 。
根据初中数学知识，我们知道 S_1(n) = \frac{n(n+1)}{2} , S_2(n) = \frac{n(n+1)(2n+1)}{6} ,S_3(n) = \frac{n^2(n+1)^2}{4} ，这些分别是关于 n 的 2,3,4 次多项式。
于是我们猜想 S_k(n) 一定能表示成关于 n 的 k+1 次多项式。
考虑第二类斯特林数，对通常幂进行转化
\begin{aligned}
i^k = \sum\limits_{j=0}^{k} \binom{i}{j} \begin{Bmatrix}k\\j\end{Bmatrix} j! = \sum\limits_{j=0}^{k} \begin{Bmatrix}k\\j\end{Bmatrix} i^{\underline{j}}
\end{aligned}
带入 S_k(n) 中可得
\begin{aligned}
&\sum_{i=0}^{n} i^k \\
=& \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{k} \begin{Bmatrix}k\\j\end{Bmatrix} i^{\underline{j}} \\
=& \sum\limits_{j=0}^{k} \begin{Bmatrix}k\\j\end{Bmatrix} \sum\limits_{i=j}^{n} i^{\underline{j}} \\
=& \sum\limits_{j=0}^{k} \begin{Bmatrix}k\\j\end{Bmatrix} j!\sum\limits_{i=j}^{n} \binom{i}{j} \\
=& \sum\limits_{j=0}^{k} \begin{Bmatrix}k\\j\end{Bmatrix} j!\sum\limits_{i=0}^{n-j} \binom{i+j}{j} \\
=& \sum\limits_{j=0}^{k} \begin{Bmatrix}k\\j\end{Bmatrix} j!\binom{n+1}{j+1} \\
=& \sum\limits_{j=0}^{k} \begin{Bmatrix}k\\j\end{Bmatrix} \frac{(n+1)^{\underline{j+1}}}{j+1}
\end{aligned}
由此，我们证明了 S_k(n) 是关于 n 的 k+1 次多项式。
所以我们只需要求出 S_k(1) ,S_k(2) , \cdots , S_k(k+2) 这 k+2 个点的点值，然后拉格朗日插值一下，就可以求出 S_k(n) 了。
那么拉格朗日插值的式子就是
S_k(n) = \sum\limits_{i=1}^{k+2} S_k(i) \prod\limits_{j\neq i} \frac{n-j}{i-j}
然后对于 \prod n-j 预处理一下，发现 \prod i-j 实际上一个数的阶乘乘上 (-1) 的一个数次方，分别算一下就可以 O(k\log k) 了。