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

2020-05-18 15:26:16


首先,感谢 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. 常数有显著提升