题解 P5050 【【模板】多项式多点求值】
Elegia
·
·
题解
首先，感谢 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。具体来说，初等矩阵中主要分为：
-
-
我们考虑给定一组 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) 过程：
- 对整体进行分治，维护对于左右 \frac n2 两部分的 (u_1, L), (u_2, R)，即分子和分母部分，然后合并为 (uR+vL, LR)。
- 最终，计算 \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-x_i x) 之乘积。
- 对于要求值的 m-1 次多项式，我们对其进行计算 \mathbf {MUL} (P^{-1} \bmod x^{m})^\mathsf T \mathbf v，然后保留前 n 位。
- 从线段树自顶向下递归，令下传的两部分向量 \mathbf l = \mathbf{MUL}(R)^\mathsf T\mathbf v,\mathbf r = \mathbf{MUL}(L)^\mathsf T\mathbf v
- 最终，得到的叶节点的向量长度均为 1，对应于该处的点值。
新的算法有以下优点：
- 不需要写多项式取模
- 常数有显著提升