二月 24, 2019 · OI 算法
多项式多点求值与快速插值学习笔记
多点求值我们若求一个一次函数 $f(x) = ax + b$ 在 $x_0$ 处的值，可以拿 $f(x)$ 对 $(x - x_0)$ 取模，得到的零次多项式即在 $x_0$ 处的点值，容易证明其正确性。 考虑分治，假设我们需要求 $x_l$ ~ $x_r$ 处的点值，可以通过当前的 $f(x)$ 对 $\prod_{i=l}^{mid} (x-x_i)$ 取模得到递归到 $x_{mid + 1}$ ~ ...
二月 24, 2019 · OI 算法
多项式多点求值与快速插值学习笔记
多点求值我们若求一个一次函数 $f(x) = ax + b$ 在 $x_0$ 处的值，可以拿 $f(x)$ 对 $(x - x_0)$ 取模，得到的零次多项式即在 $x_0$ 处的点值，容易证明其正确性。 考虑分治，假设我们需要求 $x_l$ ~ $x_r$ 处的点值，可以通过当前的 $f(x)$ 对 $\prod_{i=l}^{mid} (x-x_i)$ 取模得到递归到 $x_{mid + 1}$ ~ ...