多项式多点求值

jiazhaopeng · 2020-12-25 01:43:07 · 个人记录

给一 n 次多项式 F(x)， m 次询问，每次求 F(x_i) 的值。
1 \le n,m \le 64000

EI,rqy

方法：转置原理

通过调整（补常数项，补询问），我们能够让 n=m。

接下来可能会用到许多线性代数的东西。

转置的意思是行列互换，原来 (i,j) 变为现在的 (j,i)。
如果 A = E_1E_2E_3，那么 A^T = E_3^TE_2^TE_1^T。
初等行变换共三种：x += cy,x *= c,swap(x,y)。其中 x += cy 的矩阵为对角矩阵的第 x 行第 y 列多了个 c，x *= c 的矩阵为对角矩阵的第 x 行第 x 列的系数为 c，swap(x,y) 的矩阵为对角矩阵的第 x 行为 1 的位置出现在了第 y 列，第 y 行为 1 的位置出现在了第 x 列。这三种变换的转置分别为 y += cx，不变，不变。
所有对某个矩阵 M 进行的线性变换操作均可以看作 M 和一个个初等行变换矩阵相乘的形式（我们一般认为相乘为左乘，即将初等行变换矩阵一个个地放到左边）
多个初等行变换依次进行可以被合并拆分，具有结合律，这些矩阵的转置可以看作倒着做每个变换的转置矩阵。但是多个初等变换同时进行有时候不能被拆分，如 h_1 += h_2,h_2 += 2h_3,h_3 += 3h_1，拆分后的变量就变了，只能把它们写到一个矩阵里。这种矩阵的转置可以看作每个变换的转置矩阵同时进行。
一个多项式通常可以看作一个列向量。一个多项式乘常多项式可以看作线性变换，比如 f(x)g(x) 可以将其拆为 f(x)g_ix^i 相加，而 f(x)g_ix^i 可以看作将 f(x) 这一列的每一个元素乘上一个 g_i 的常数，加到了其下面 i 行的那个位置。
多项式 F 乘常多项式 G 还可以看作这个过程：F 通过 DFT 变为 F'，和常多项式的点值（也是常数）G' 对应相乘，再 IDFT 变为 F。其中 DFT，对应相乘，IDFT 这三种操作都是线性的，且其转置都是自身（DFT 本质上是一个第 i 行第 j 列为 \omega_n^{(i-1)(j-1)} 的矩阵，显然其转置不变，IDFT 同理，而对应相乘可以看作若干 x *= c 依次进行或同时进行）

好的让我们进入正题。

我们要求的是这样的一个矩阵（列向量）：

\begin{pmatrix} 1& x_0& x_0^2& \cdots& x_0^{m-1}\\ 1& x_1& x_1^2& \cdots& x_1^{m-1}\\ 1& x_2& x_2^2& \cdots& x_2^{m-1}\\ \vdots& \vdots& \vdots& \ddots& \vdots\\ 1& x_{n-1}& x_{n-1}^2& \cdots& x_{n-1}^{m-1}\\ \end{pmatrix} f

其中 x_i 为要求的第 i 个点值，在这里我们认为它是固定的，即与 f 无关的。f 为输入的系数向量（列矩阵）

其中左边的叫做范德蒙矩阵，记作 V。我们发现 Vf 并不好求，但是 V^Tf 很好求，即：

\mathbf V(x_0, x_1,\dots, x_{n-1})^{\mathsf T} \mathbf f = \begin{bmatrix} 1& 1& 1& \cdots& 1\\ x_0& x_1& x_2& \cdots& x_{n-1}\\ \vdots& \vdots& \vdots& \ddots& \vdots\\ x_0^{n-1}& x_1^{n-1}& x_2^{n-1}& \cdots& x_{n-1}^{n-1} \end{bmatrix}\mathbf f

很好求。为什么呢？我们仔细观察，发现这个东西用多项式来表达为：

\sum_{i=0}^n f_i\sum_{j=0}^n x_i^jx^j\\ =\sum_{i=0}^nf_i\frac{1}{1-x_ix}

这个东西可以通过分治套 NTT 暴力通分搞出分子和分母，然后多项式求逆得到答案。复杂度为 O(n \log^2 n)。然而这样做一定是假的，因为它求出的是 V^Tf，这个没有任何意义。但是这个求 V^T 的过程对求 V 的过程很有启发。

考虑到 (V^T)^T=V ，我们只需要把刚才那个“假”做法中的所有初等行变换记录下来，反过来乘其置换矩阵即可。但是太麻烦了。我们考虑这个操作在我们人类眼中是个什么样子的存在。

首先分解 V^Tf。我们那个假做法为：[除以分母] \times [分治NTT求分子] \times f，其中 [除以分母] 和 [分治NTT求分子] 都可以看作矩阵。

具体地讲，我们设常多项式 g(x) = \prod_i 1-x_ix，即分母，那么 [除以分母] 这个操作实际上为 [IDFT] \times [与 g^{-1} 对应位相乘] \times [DFT]。[分治NTT求分子] 这个操作比较复杂：

递归到叶子节点时：ans_x=f_i
非叶节点：
- 递归儿子求儿子的分子 ans_{l},ans_r 和儿子的分母 g_{l},g_r
- ans_x = ans_lg_r+ans_rg_l

如果我们认为列向量 f 是由原来叶子上的一个个初值组成的，那么这些操作（主要是非叶节点的操作）都可以看作是对 f 的一系列线性变换。或者说，是若干多项式逐渐合并成为一个多项式的过程。

现在我们要探寻 V^T 的转置矩阵 (V^T)^T，它应该是：

(([IDFT] \times [对应乘g的点值] \times [DFT]) \times [自下而上递归求分子])^T\\ =[自上而下反过来变换]^T \times [DFT] \times [对应乘] \times [IDFT]

右面那部分比较好算，可以算得：

[DFT] \times [对应乘] \times [IDFT] \times f = h

现在考虑 [自上而下反过来变换]^T 究竟是什么：

根节点：h_x
非叶节点：
- 分别拿着 h_l 和 h_r 递归到俩儿子处继续算
叶节点：Res_x

这些操作可以看作是一个多项式逐渐分裂分裂变成一堆零次多项式，而那些零次多项式所组成的矩阵即为所求矩阵 Vf。

于是一切都结束了。算法流程为：

计算分母 g，注意保留其在每个分治节点上的值。
求 g^{-1}，其转置为自身。
定义 \times ^T 表示那种奇葩的先 IDFT 再乘再 DFT 的乘法。计算 g^{-1} \times^T f（左乘）放在根节点准备分治。
我们称 h 为上面传下来的多项式，根节点为 g^{-1} \times^T f，那么计算 h \times^T g_r 扔到左面递归，计算 h \times^T g_l 扔到右面递归。
最后叶子节点存的多项式即为答案。