题解 P5050 【【模板】多项式多点求值】

首先，感谢 rushcheyo, negiizhao, Created_Equal 于 IOI 2020中国国家集训队第一阶段作业《转置原理的简单介绍》中，对于本算法以及转置原理的引入和介绍工作。原本该文章的内容会由他们在 WC2020 中进行分享，可惜的是计划赶不上变化。 下面介绍的方法是多点求值的一种更快，代码量更小的算法。为了建立对其有外延性的理解，我们首先要简单解释转置原理，或称特勒根原理（Tellegen's Principle）的核心思想： 对于矩阵 $\mathbf M$ 和任一向量 $\mathbf v$，为了优化计算 $\mathbf {Mv}$，转置原理指出我们可以先考察计算 $\mathbf M^{\mathsf T}\mathbf v$ 的方法。即矩阵的转置。设有矩阵 $\mathbf M = {\mathbf E}_1{\mathbf E}_2 \cdots {\mathbf E}_k$ 这一分解，其中 ${\mathbf E}_i$ 均为初等矩阵，那么我们有 ${\mathbf M}^\mathsf T = {\mathbf E}_k^\mathsf T\cdots {\mathbf E}_2^\mathsf T{\mathbf E}_1^\mathsf T$。具体来说，初等矩阵中主要分为： 1. $\mathbf {Ev}$ 的效果是让向量 $\mathbf v$ 的第 $i$ 位乘以 $c$，那么其转置的效果也是一样的。 2. $\mathbf {Ev}$ 的效果是让向量 $\mathbf v$ 的第 $i$ 位乘以 $c$ 加到第 $j$ 位，那么其转置的效果就是让向量的第 $j$ 位乘以 $c$ 加到第 $i$ 位上。 我们考虑给定一组 $x_0 \sim x_{n-1}$，那么对于任给一个 $n-1$ 次多项式的写作系数向量的形式，转化为各位置点值的变换是线性变换，可写作矩阵 $$ \mathbf V(x_0, x_1,\dots, x_{n-1})=\begin{bmatrix} 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{bmatrix} $$ 考虑其转置 $\mathbf V(x_0, x_1,\dots, x_{n-1})^{\mathsf T} \mathbf v = \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 v$ 我们发现，其转置所求的实际上就是 $$ [x^k]\sum_{i=0}^{n-1} \frac{v_i}{1- x_i x} $$ 而我们知道为了求这个，我们常采取的做法是这样的 $\Theta(n\log^2n)$ 过程： 1. 对整体进行分治，维护对于左右 $\frac n2$ 两部分的 $(u_1, L), (u_2, R)$，即分子和分母部分，然后合并为 $(uR+vL, LR)$。 2. 最终，计算 $\frac{u_1}{P}$。 注意，中间所有的分母仅仅是这个线性变换中矩阵里的东西，是对于 $u$ 的线性变换。 接下来我们有必要注意一下一个重要的线性变换：多项式乘法作用 $\mathbf{MUL}(A) \mathbf v$ 的转置 $\mathbf{MUL}(A)^\mathsf T\mathbf v$。 对于多项式 $A(x)=\sum_i a_ix^i$，我们知道每个 $v_j$ 乘上 $a_i$ 会贡献给 $i+j$ 位置。因而转置后就是 $v_j$ 乘上 $a_i(i\le j)$ 会贡献给 $j-i$ 位置。因此这是另一个方向的卷积形式。此外，若原变换不溢出，则转置变换的 FFT 长度也是 $n$ 而不是 $2n$，因为循环卷积溢出的部分我们正好不要。 因此，我们得到的新的多点求值做法如下： 1. 对整体进行分治，维护出线段树对应的每个子树的 $(1-x_i x)$ 之乘积。 2. 对于要求值的 $m-1$ 次多项式，我们对其进行计算 $\mathbf {MUL} (P^{-1} \bmod x^{m})^\mathsf T \mathbf v$，然后保留前 $n$ 位。 3. 从线段树自顶向下递归，令下传的两部分向量 $\mathbf l = \mathbf{MUL}(R)^\mathsf T\mathbf v,\mathbf r = \mathbf{MUL}(L)^\mathsf T\mathbf v$ 4. 最终，得到的叶节点的向量长度均为 $1$，对应于该处的点值。 新的算法有以下优点： 1. 不需要写多项式取模 2. 常数有显著提升