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

对于一个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)逆元和前缀后缀积在线性时间内完成。

发表评论

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