前置知识:

  • 多项式乘法
  • 多项式取模
  • 拉格朗日插值

多点求值

考虑我们求一个一次函数 f(x) = ax + bx_0 处的值。可以拿 f(x)(x - x_0) 取模,得到的零次多项式即在 x_0 处的点值,容易证明其正确性。

考虑分治,假设我们需要求 x_l ~ x_r 处的点值,可以通过当前的 f(x)\prod_{i=l}^{mid} (x-x_i) 取模得到递归到 x_{mid + 1} ~ x_r 的多项式,对 \prod_{i=mid+1}^r (x-x_i) 取模得到递归到 x_l ~ x_mid 的多项式。其中上面两个连乘积可以通过分治 + 多项式乘法得到,保存在线段树状结构中。若多项式项数与待求值点数相同则在叶子节点我们可以直接获取点值。

快速插值

考虑朴素的拉格朗日插值

f(x) = \sum_{i=1}^n y_i \prod_{j\not=i} \frac {x-x_j} {x_i - x_j}

1、 考虑求下半部分即对于每个 i \in [1, n] ,求出 \prod_{j\not=i} (x_i - x_j)

\prod_{j\not=i} (x_i - x_j) = \lim_{x \rightarrow x_i} \frac {\prod_{j=1}^n (x_i - x_j)} {x - x_i}

设分子上半部分为 g(x) ,由于上下均为不定式,用洛必达法则得

\lim_{x \rightarrow x_i} \frac {g(x)} {x - x_i} = \lim_{x \rightarrow x_i} g'(x) = g'(x_i)

g'(x) 多点求值即可。

2、 考虑现在我们可以把原式化为

f(x) = \sum_{i=1}^n \frac {y_i} {\prod\limits_{j\not=i} (x_i - x_j)} \prod_{j\not=i} (x-x_j)

其中 \frac {y_i} {\prod_{j\not=i} (x_i - x_j)} 我们已知,可以用 z_i 来表示

f(x) = \sum_{i=1}^n z_i \prod_{j\not=i} (x-x_j)

仍然考虑分治,

\begin{aligned} f_{l \rightarrow r}(x) &= \sum_{i=l}^r z_i \prod_{j=l,j\not=i}^r (x-x_j) \\ &= \sum_{i=l}^{mid} z_i \prod_{j=l,j\not=i}^r (x-x_j) + \sum_{i=mid+1}^{r} z_i \prod_{j=l,j\not=i} (x-x_j) \\ &= \sum_{i=l}^{mid} z_i \prod_{j=l,j\not=i}^{mid} (x-x_j) \times \prod_{j=mid+1,j\not=i}^{r} (x-x_j) + \sum_{i=mid+1}^{r} z_i \prod_{j=mid+1,j\not=i}^{r} (x-x_j) \times \prod_{j=l,j\not=i}^{mid} (x-x_j) \\ &= f_{l \rightarrow mid}(x) \prod_{j=mid+1,j\not=i}^{r} (x-x_j) + f_{mid+1 \rightarrow r}(x) \prod_{j=l,j\not=i}^{mid} (x-x_j) \\ \end{aligned}

可以直接调用之前分治 + 多项式乘法的结果避免重复调用。

多项式取模 拉格朗日插值 多项式多点求值 多项式快速插值