Hellc

本文主要讲述了多项式的定义，系数表达及点值表达，两种表达方式的转换，优化多项式乘法的思路等问题。

主要是作为学习 FFT 的预备知识。

多项式

以下形式的 $A(x)$ 称为「多项式」。

$$A(x) = \sum_{i = 0}^{n - 1}a_ix^i$$

即多项式是若干个 $x$ 的幂次与其对应系数乘积的和。

该多项式的最高项次数为 $n - 1$，将其称为多项式的「次数」，即 $A(x)$ 可以称作次数为 $n - 1$ 的多项式。

任何一个严格大于多项式次数的整数，称为多项式的「次数界」，即 $A(x)$ 可以称作次数界为 $n, n + 1, n + 2, \cdots$ 的多项式。

举个例子的话，$A(x) = 1 + 3x + 3x^2$ 是一个次数为 $2$，次数界大于 $2$ 的多项式。

多项式的表达

一般来说，我们有「系数表达」和「点值表达」两种方法来表示一个多项式。

系数表达

即用系数来表达多项式，这也是我们平常所用的方法。

可以将多项式的系数看做一个 $n$ 维（列）向量： $$\vec a = (a_0, a_1, \cdots, a_{n - 1})$$ 则 $\vec a$ 称作多项式的「系数表达」。

如上文中例子的系数表达即为 $(1, 3, 3)$。

点值表达

通俗地说，点值表达就是取 $n$ 个（互不相同的）数代进 $A(x)$ 去求出值来，这样的得到 $n$ 个点，即为多项式的「点值表达」。

用数学符号来表示： $$\{(x_i, y_i) \mid i \in [0, n), i \in \mathbb Z\}$$ 其中 $y_i = A(x_i)$。

如上文中例子的一个点值表达为 ${(0, 1), (1, 7), (2, 19)}$。

多项式的点值表达不是唯一的，因为你可以任意更换求值的点（但总应保证它们是互不相同的），但 $n$ 个点的点值表达一定可以确定一个次数为 $n - 1$ 的多项式（下文中会证明这一点）。

相互转换

系数表达 -> 点值表达

按照定义，我们取 $n$ 个不同的数代入多项式求值即可，如果采用秦九韶算法（又称霍纳法则）进行单次求值，那么总的复杂度是 $O(n^2)$。

秦九韶算法，可以在 $O(n)$ 的时间内对多项式单点求值，基于以下公式。

$$A(x_0) = a_0 + x_0(a_1 + x_0(a_2 + \dots + x_0(a_{n-2} + x_0a_{n-1})\dots))$$

我们不妨把这个过程称之为多项式的「求值」。

点值表达 -> 系数表达

由点值表达到系数表达的转换，称为多项式的「插值」。

多项式的插值实际上描述了一个解线性方程组的过程，考虑以下矩阵方程。

$$\left[ \begin{matrix} 1 & x_0 & x_0^2 & \cdots & x_0^{n-1} \\ 1 & x_1 & x_1^2 & \cdots & x_1^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1} \end{matrix} \right] \left[ \begin{matrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{matrix} \right] = \left[ \begin{matrix} y_0 \\ y_1 \\ \vdots \\ y_{n-1} \end{matrix} \right]$$

一个可行的方法是求出左边矩阵的逆矩阵，乘到右边去，就可以获得系数表达。

左边这种形式的矩阵称为「范德蒙德矩阵」，不妨记作 $V(x_0, x_1, \cdots, x_{n - 1})$，那么有 $\vec a = V(x_0, x_1, \cdots, x_{n - 1})^{-1} \vec y$。

但一个问题是，这个矩阵是否存在逆矩阵，或者说这个方程是否有且有唯一解，。

为了解决这个问题，我们考虑左边矩阵的行列式，由「范德蒙德矩阵」的性质，可以证明：

$$\det(V(x_0, x_1, \cdots, x_{n - 1})) = \prod_{0 \leq j \lt k \leq n - 1}(x_k - x_j)$$

那么，若 $x_i$ 互不相等，则以上行列式必不为零，也就是说该矩阵可逆，这也就证明了，$n$ 个点的点值表达可以唯一确定一个次数为 $n - 1$ 的多项式。

因为我们可以在 $O(n^3)$ 的时间内完成矩阵求逆，所以我们得到了一个 $O(n^3)$ 的插值算法。

更优越一点的方法是使用「拉格朗日插值法」，基于如下公式：

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

可以看出，通过该公式构造的 $A(x)$ 是满足要求的，对于任意给定的 $k$，将 $x_k$ 代入，和式中只有 $y_k$ 这一项不为零，且系数为 $1$。

仍以上文中那个多项式的点值表达为例，${(0, 1), (1, 7), (2, 19)}$，根据公式，可以构造出：

$$A(x) = 1 \frac {(x - 1)(x - 2)} {(0 - 1)(0 - 2)} + 7 \frac {(x - 0)(x - 2)} {(1 - 0)(1 - 2)} + 19 \frac {(x - 0)(x - 1)} {(2 - 0)(2 - 1)}$$

读者不妨自行将 $x = 0, 1, 2$ 代入上式以验证其正确性（与这个构造方法的精巧），该式的化简结果确为 $A(x) = 1 + 3x + 3x^2$。

使用「拉格朗日插值法」的复杂度是 $O(n^2)$ 的。

多项式的基本运算

我们为什么要花费这么大的力气在这两种表达形式中转换呢，显然这是因为这两种表达形式各有优点。

多项式的加减法运算较为简单，在系数表达下，就是对应的系数相加减，在点值表达下，就是对应求值点的式值相加减，复杂度均为 $O(n)$，不过多叙述。

多项式乘法在系数表达下相对复杂，定义如下：

若有 $$A(x) = \sum_{i = 0}^{n - 1}a_ix^i \\ B(x) = \sum_{i = 0}^{n - 1}b_ix^i$$ 则 $C(x) = A(x)B(x)$ 运算如下： $$C(x) = \sum_{i = 0}^{2n - 2}c_ix^i$$ 其中 $$c_i = \sum_{k = 0}^ia_kb_{i - k}$$

按照定义进行，在系数表达下，计算多项式乘法的复杂度为 $O(n^2)$。

然而，在点值表达下，多项式乘法依旧简单，只要把对应求值点的式值相乘即可，复杂度 $O(n)$。要注意的是，由于 $C$ 的次数界是 $2n$ 的，所以我们需要将 $A$ 和 $B$ 的点值表达扩展到 $2n$ 才可以。

为了快速地计算系数表达下的多项式乘法，我们采取这样的策略：

首先将系数表达转换为点值表达（求值），然后在点值表达下进行 $O(n)$ 的多项式乘法，然后再从点值表达转换回系数表达（插值）。

事实上，行文至此，这个策略看上去并不能加速我们的计算，因为我们目前所提及的求值和插值均是 $O(n^2)$ 的。

一种优化的思路是，不是任选 $n$个毫无关联的值来进行求值与插值，而是通过选取特定的值，利用它们之间的联系来降低复杂度。

快速傅里叶变换 (Fast Fourier Transform, FFT) 就是运用了这一思路，使用单位复数根作为求值点对多项式进行 离散傅里叶变换 (Discrete Fourier Transform, DFT) （求值）和 逆离散傅里叶变换 (Inverse Discrete Fourier Transform, IDFT)（插值），从而加速到 $O(n \log n)$。

关于 FFT 的细节，在另一篇单独的文章中有具体的阐述，~~参见快速傅里叶变换 - 学习笔记。~~ 其实还没写完 QWQ。