下降幂多项式

今天听讲课的时候听到了这个有趣的东西，记录一下防止忘记。

下降幂多项式

形如 $f(x) = \sum_{i = 0}^{n}a_i x^{\underline{i} }$ 的多项式被称为下降幂多项式。

它有一些绝妙的性质。

求值：可以快速求一段 $0 \sim m$ 内的所有点值。

插值：可以根据 $0 \sim n + 1$ 的点值简单地插出这个下降幂多项式。

对于求值，考虑

$$\begin{aligned} f(x) & = \sum_{i = 0}^{n} a_i x^{\underline{i} } \\ & = x!\sum_{i = 0}^{n} a_i \frac{1}{(x - i)!} \end{aligned}$$

只需要求 $f$ 和 $\exp$ 的卷积，乘上 $x!$ 即可计算出 $f(x)$。

对于插值，考虑

$$\begin{aligned} f(x) & = \sum_{i = 0}^{n} a_i x^{\underline{i} } \\ & = \sum_{i = 0}^{x} \binom{x}{i} i! a_i \end{aligned}$$

二项式反演。

$$\begin{aligned} a_x & = \frac{1}{x!} \sum_{i = 0}^{x} (-1)^{x - i} \binom{x}{i} f(i) \\ & = \sum_{i = 0}^{x}\frac{f(i)}{i!} \cdot \frac{(-1)^{x - i}}{(x - i)!} \end{aligned}$$

这样就用 $0 \sim n$ 处的点值插出了所有 $a_i$。只需要一次卷积。

普通多项式转下降幂多项式

考虑分治。

设 $f$ 为待转换的普通多项式，$g$ 为转换后的下降幂多项式。

将 $f_{l\sim mid}$ 与 $f_{mid + 1 \sim r}$ 递归处理，求出 $g_{l\sim mid}$ 和 $g_{mid + 1 \sim r}$。

设 $m = mid - l + 1$，$len = r - l + 1$。

那么 $g_{l\sim r} = g_{l\sim mid} + x^m \cdot g_{mid + 1 \sim r}$。

考虑 $x^{m} \cdot g_{\ldots}$ 怎么求。其中 $g$ 已经是下降幂多项式了。

我们可以求出 $x^{m}$ 与 $g$ 在 $0 \sim len - 1$ 处的所有点值，$x^m$ 可以暴力，$g$ 可以采用上述方法处理。

然后将点值两两相乘得到 $x^m\cdot g$ 的点值，再插值回去即可得到 $x^m\cdot g$。

这样我们就将 $g_{l\sim mid}$ 和 $g_{mid + 1 \sim r}$ 合并成了 $g_{l\sim r}$。

下降幂多项式转普通多项式

留坑待填。