线性插值

感觉我正在日益沦为一个搬运工...

线性插值是指这样一个问题：给定整数 $n, m$ ，以及一个 $n$ 次多项式 $f$ 在 $0, 1, 2, \dots, n - 1$ 处的点值，即 $f (0), f (1), f (2), \dots, f (n - 1)$ ，希望能在关于 $n$ 的线性时间内求出 $f (m)$ 。 $n \leq 10^{6}, m \leq 10^{18}$ 。

利用多项式多点插值并求一次点值可以做到 $O (n \log^{2} n)$ ，但显然是过不去的。

我们考虑多项式 $f$ 的牛顿级数，设其为 $c$ ，即：

\sum_{i = 0}^{n - 1} f_{i} x^{i} = \sum_{i = 0}^{n - 1} c_{i} (\binom{x}{i})

那么对于 $m = 0, 1, 2, \dots, n - 1$ ，显然有：

f (m) = \sum_{i = 0}^{n - 1} c_{i} (\binom{m}{i})

注意到当 $i \geq m$ 时 $(\binom{m}{i})$ 为 $0$ ，于是修改求和上限：

f (m) = \sum_{i = 0}^{m} c_{i} (\binom{m}{i})

这就是经典的二项式反演的形式，于是我们就得到：

c_{i} = \sum_{j = 0}^{i} (- 1)^{i - j} (\binom{i}{j}) f (j)

进回带到求和上限为 $n - 1$ 的式中，于是有：

f (m) = \sum_{i = 0}^{n - 1} ((\binom{m}{i}) \sum_{j = 0}^{i} (- 1)^{i - j} (\binom{i}{j}) f (j))

套路一波，将对 $j$ 的求和放到外面：

f (m) = \sum_{j = 0}^{n - 1} (f (j) \sum_{i = j}^{n - 1} (- 1)^{i - j} (\binom{m}{i}) (\binom{i}{j}))

为了直观，我们用 $i$ 替换 $i - j$ ：

f (m) = \sum_{j = 0}^{n - 1} (f (j) \sum_{i = 0}^{n - 1 - j} (- 1)^{i} (\binom{m}{i + j}) (\binom{i + j}{j}))

利用 $(\binom{m}{i + j}) (\binom{i + j}{j}) = (\binom{m}{j}) (\binom{m - j}{i})$ 进行替换，得到：

f (m) = \sum_{j = 0}^{n - 1} (f (j) \sum_{i = 0}^{n - 1 - j} (- 1)^{i} (\binom{m}{j}) (\binom{m - j}{i}))

于是 $(\binom{m}{j})$ 可以放到前面：

f (m) = \sum_{j = 0}^{n - 1} (f (j) (\binom{m}{j}) \sum_{i = 0}^{n - 1 - j} (- 1)^{i} (\binom{m - j}{i}))

现在考虑求出下面的式子的封闭形式：

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

首先是应用上指标反转使 $(- 1)^{i} (\binom{m}{i}) = (\binom{i - m - 1}{i})$ ：

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

考虑加入一个数 $(\binom{- m - 1}{- 1}) = 0$ ：

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

裂项：

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

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

一直重复，直到只剩下：

(\binom{n - m - 1}{n - 1})

再进行上指标反转：

(- 1)^{n - 1} (\binom{m - 1}{n - 1})

于是原式终于可以简化为：

f (m) = \sum_{j = 0}^{n - 1} (f (j) (\binom{m}{j}) (- 1)^{n - 1 - j} (\binom{m - 1 - j}{n - 1 - j}))

整理，得：

f (m) = \sum_{i = 0}^{n - 1} (- 1)^{n - 1 - i} (\binom{m}{i}) (\binom{m - 1 - i}{n - 1 - i}) f (i)

用阶乘展开组合数：

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

继续整理：

f (m) = m^{\underset{―}{n}} \sum_{i = 0}^{n - 1} \frac{(- 1)^{n - 1 - i}}{(m - i) i! (n - 1 - i)!} f (i)

于是就可以做了， $m - i$ 的逆元可以用与预处理阶乘逆元的类似方法做到线性。总复杂度是 $O (n)$ 。

$u p d$ ：被强大的姐姐打脸了...其实直接用拉格朗日插值公式即可推出和上面一样的东西...~~所以这篇文章只是想说数学真奇妙。~~