插值 - Blog | qzkszj

其实一个多项式 $f(x)$ 被表示成广泛一点的形式应该是这样的：

f(x)=\sum_ i g_ i(x) \times c_ i

平常我们写的多项式是自然数幂的形式，也就是 $g_ i(x)=x^ i$

插值的定义是在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数据点。

这里组合数意义用小学教的方法表示是因为这样第一项为负数的时候依然有意义（无组合意义）

\sum_ {i=0}^ n(-1)^ i(^ m_ i)

=\sum_ {i=0}^ n (-1)^ i\frac{m \times (m-1) \times \cdots \times (m-i+1)}{i!}

=\sum_ {i=0}^ n\frac{-m \times (-m+1) \times \cdots \times (-m+i-1)}{i!}

=\sum_ {i=0}^ n(^ {-m+i-1}_ i)

这一步证明合集有，就是前面加一项 $(^ {-m-1}_ {-1})$

=(^ {n-m}_ n)

多项式有其他的表示方式，这里用到的是这样的：

f(k)=\sum_ i(^ k_ i)c_ i

现在我们知道 $f(1\cdots n)$ 的值是 $a_ {1\cdots n}$ （n足够）,求 $f(k)$ 。
当 $n$ 比较小的时候，我们可以通过偏序函数的容斥把每一项 $c_ i$ 都求出来：

c_ i=\sum_ {j=0}^ i(-1)^{i-j}(^ i_ j)a_ j

复杂都 $O(N^ 2)$ ，没有更好的解决方法，于是只能将式子带入。

f(k)=\sum_ i(^ k_ i)c_ i

=\sum_ {i=0}^ n(^ k_ i)\sum_ {j=0}^ i(-1)^{i-j}(^ i_ j)a_ j

=\sum_ {i=0}^ n\sum_ {j=0}^ i(-1)^ {i-j}(^ k_ i)(^ i_ j)a_ j

$(^a_ c)(^c_ b)$ 的组合意义可以理解为在一个大范围内确定大圈，然后再里面找一个小圈。
这样等价于找一个小圈，再枚举可以贡献到多少个大圈上。
顺便交换一下 $i,j$ 的枚举顺序。

=\sum_ {j=0}^ n\sum_ {i=j}^ n(-1)^ {i-j}(^ k_ j)(^ {k-i}_ {i-j})a_ j

=\sum_ {j=0}^ n(^ k_ j)a_ j\sum_ {i=j}^ n(-1)^ {i-j}(^ {k-i}_ {i-j})

有点乱，重定义一下i=j,j=i-j(等号后面都是原来的i,j)

=\sum_ {i=0}^ n(^ k_ i)a_ i\sum_ {j=0}^ {n-i}(-1)^ j (^ {k-i}_ j)

发现后面的sum式子其实是一个前面说的交错和的形式，所以：

=\sum_ {i=0}^ n(^ k_ i)a_ i(^ {n-k}_ {n-i})

注意到n特别小，所以每次求的时候就可以快速预处理一下，就 $O(n)$ 了。