特殊多项式在整点上的线性插值方法

对于一个$k$次的多项式$F(x)$,已知$F(0),F(1),F(2),…,F(k)$,求出$F(n)$

这个问题可以在$O(k)$的时间复杂度内解决。下面将介绍具体做法。
我们考虑用组合数表示$F(x)$,因为$\binom{x}{m}$是一个$m$次的多项式,所以$\binom{x}{0},\binom{x}{1},…,\binom{x}{k}$互相线性无关,所以我们可以用它们的线性组合来表示$F(x)$。
$$
\begin{equation}
F(x)=\sum_{i=0}^k\binom{x}{i}a_i
\end{equation}
$$
对于$x$<$i$我们知道$\binom{x}{i}=0$。所以,上面的式子可以写成 $$ F(x)=\sum_{i=0}^x\binom{x}{i}a_i $$ 通过反演可以得到 $$ a_i=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}F(j) $$ 再将其回代入最开始的式子中,得到 $$ \begin{aligned} F(x)&=\sum_{i=0}^k\binom{x}{i}\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}F(j)\\ &=\sum_{j=0}^kF(j)\sum_{i=0}^{k-j}(-1)^{i}\binom{x}{i+j}\binom{i+j}{j} \end{aligned} $$ 因为有 $$ \begin{aligned} \binom{x}{i+j}\binom{i+j}{j}&=\frac{x!}{(x-i-j)!(i+j)!}\cdot\frac{(i+j)!}{i!j!}\\ &=\frac{x!}{j!}\cdot \frac{1}{i!(x-i-j)!}\\ &=\frac{x!}{(x-j)!j!}\cdot \frac{(x-j)!}{i!(x-i-j)!}\\ &=\binom{x}{j}\binom{x-j}{i} \end{aligned} $$ 所以,原式可化为 $$ \begin{aligned} F(x)&=\sum_{j=0}^{k}\binom{x}{j}F(j)\sum_{i=0}^{k-j}(-1)^{i}\binom{x-j}{i} \end{aligned} $$ 我们考虑后面一部分,即$\sum_{i=0}^{k-j}{(-1)}^i\binom{x-j}{i}$ 因为出现了组合数和$-1$的方幂,我们考虑组合数的上指标反转,也就是下面这个等式 $$ \binom{r}{k}=(-1)^{k}\binom{k-r-1}{k} $$ 由组合数的定义将其展开即可证明。 让我们再回到原式,不妨设$G_k(x)=\sum_{i=0}^{k}(-1)^i\binom{x}{i}$,通过上指标反转,我们可以得到 $$ \begin{aligned} G_k(x)&=\sum_{i=0}^{k}\binom{-x+i-1}{i}\\ &=\binom{-x+0-1}{0}+\binom{-x+1-1}{1}+\binom{-x+2-1}{2}+…+\binom{-x+k-1}{k}\\ &=\binom{-x+1-1}{0}+\binom{-x+1-1}{1}+\binom{-x+2-1}{2}+…+\binom{-x+k-1}{k}\\ &=\binom{-x+2-1}{1}+\binom{-x+2-1}{2}+…+\binom{-x+k-1}{k}\\ &…\\ &=\binom{-x+k-1}{k-1}+\binom{-x+k-1}{k}\\ &=\binom{-x+k}{k} \end{aligned} $$ 所以,代入原式,易得 $$ \begin{aligned} F(x)&=\sum_{j=0}^k\binom{x}{j}F(j)G_{k-j}(x-j)\\ &=\sum_{j=0}^k\binom{x}{j}F(j)\binom{-x+k}{k-j}\\ &=\sum_{j=0}^{k}(-1)^{k-j}\binom{x}{j}\binom{x-j-1}{k-j}F(j)\\ &=\sum_{j=0}^{k}(-1)^{k-j}\frac{x!}{j!(x-j)!}\cdot\frac{(x-j-1)!}{(x-k-1)!(k-j)!}\cdot F(j)\\ &=\sum_{j=0}^{k}(-1)^{k-j}\frac{1}{j!(x-j)(k-j)!}\cdot\frac{x!}{(x-k-1)!}\cdot F(j)\\ \end{aligned} $$ 上式中前面分式中的阶乘可以通过预处理完成,后面的可以通过预处理相除后剩下的项完成。 $x-j$的逆元可以通过处理$x\cdot(x-1)\cdot(x-2)…(x-k)$逆元和前缀后缀积在线性时间内完成。

发表评论

电子邮件地址不会被公开。 必填项已用*标注