终于学转置原理了，之前一直听 zhy 糊多项式题不知道他在讲写啥。
自己的多项式水平长期停留在多项式除法，直到今天做互测时被迫学了怎么去多点求值。正式比赛大概率不考（吧？）所以学来娱乐一下。
普通多点求值算法
思想很妙，效率很逊。代码不写了因为我连多项式取模都忘了怎么写了。
考虑类似 CRT 和拉插的思想，对于点值集合 \(P\) 构造多项式 \(M_P(x)=\prod_{c\in P}(x-c)\)。这样就有了 \(\forall x\in P,M_P(x)=0\)。
然后考虑分治计算贡献，每次将点值均匀分成两个集合 \(P_0,P_1\)，对于当前多项式 \(F\)，多项式取模一下将其表示为 \(F=Q_0 M_{P_0}+F_0\) 和 \(F=Q_1 M_{P_1}+F_1\)。
那么你代入 \(P_0\) 中的点值时商的贡献就被消掉了，有 \(F(x)=F_0(x)\)，这样 \(P,F\) 的规模双双减半。于是你往下递归做就可以了。\(M_P\) 可以在分治过程中递归维护出来。
每一层都带多项式取模（求逆）的 \(\log\)，总复杂度 \(O(n\log^2 n)\)，而且常数上天。
快速插值算法
多点求值本质上让我们乘上任意一个范德蒙德矩阵，而多项式操作基本上都是对于程序中变量的线性变换。这启发我们插值作为求值的逆算法也可以做到同等复杂度。
快速插值我们考虑对着拉插公式大力优化：\(F=\sum y_i \prod_{i\neq j} \frac{x-x_j}{x_i-x_j}\)。
考虑那个分母，这个东西里面似乎就是一个 \(M_{P/\{x_i\}}(x_i)\)，也就是 \(M_P(x_i)\) 除以一个 \(x_i-x_i\)，发现关键在零除零，那你发动技能“洛神”对里面大力洛必达一下，就可以得到 \(M_{P/\{x_i\}}(x_i)=M_P'(x_i)\)。也就是说你直接分治 NTT 出 \(M_P\) 之后求个导，然后再套多点求值就可以了！
剩下的相当于要计算 \(\sum \frac{y_i}{M_{P/\{x_i\}}(x_i)} \prod_{i\neq j} (x-x_j)\)，直接上经典的缺一分治，也是分治 NTT，做完了！复杂度同多点求值，常数更上一层楼！
接下来是发病时间：
啊你看这个转置原理啊，就是说多点求值作为一个线性算法时可以分解成初等行矩阵然后去转置它（\((AB)^T=B^TA^T\)）。那你也可以分解成初等行矩阵之后求逆它啊（\((AB)^{-1}=B^{-1}A^{-1}\)）。
那你可以把多点求值中的所有变量都当成向量中的变量，把算法全部描述成乘上初等行变换矩阵，然后 reverse 一下这个操作序列，再一个一个还原回去就行了。
不要提常数的事，这个做法时空都是 \(O(n\log^2 n)\) 的毫无实际意义。
转置原理
看的王总博客
上面的技术在 EI 一行人引入转置原理之后就显得过时了整个多项式内容都过时了。
多项式操作经常是线性变换，你仔细读一下 DFT 的代码就会发现你唯一做了的事要么就是将一个数的若干倍加到另一个数上，或者说交换两个数。
对于这种“线性算法”，它总能够被描述成乘上一个矩阵的样子 \(\vec{u}=A\vec{v}\)，而且我们知道了如果它是可以快速做的，那么在同等的时间复杂度内它的逆变换时可以快速做的，具体看上文“发病时间“。同理它的转置算法，也就是求 \(A^T \vec{v}\) 也是可以快速做的。
卷积算法是可以转置的，这可以看王总博客。那 DFT 呢？搞笑了，它的转置就是它自己。
直接讲讲多点求值吧。多点求值就是直接乘上任意一种范德蒙德矩阵，相当于：
\[\begin{bmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^n\\ 1 & x_2 & x_2^2 & \cdots & x_2^n\\ 1 & x_3 & x_3^2 & \cdots & x_3^n\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & x_m & x_m^2 & \cdots & x_m^n \end{bmatrix} \begin{pmatrix} f_0\\ f_1\\ f_2\\ \vdots\\ f_n \end{pmatrix} = \begin{pmatrix} g_1\\ g_2\\ g_3\\ \vdots\\ g_m \end{pmatrix} \]你把它转置，猜猜它是啥：
\[\begin{bmatrix} 1 & 1 & 1 & \cdots & 1\\ x_1 & x_2 & x_3 & \cdots & x_m\\ x_1^2 & x_2^2 & x_3^2 & \cdots & x_m^2\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ x_1^n & x_2^n & x_3^n & \cdots & x_m^n \end{bmatrix} \begin{pmatrix} g_1\\ g_2\\ g_3\\ \vdots\\ g_m \end{pmatrix} = \begin{pmatrix} f_0\\ f_1\\ f_2\\ \vdots\\ f_n \end{pmatrix} \]是你，带权等幂和问题！我们考虑先如何解决这个问题，写出 GF：
\[F(t)=\sum_{i=0}^m \frac{g_i}{1-x_it} \]这里有个求和，看起来比较棘手。我们不妨考虑通分，用分治 NTT 去处理：
\[\frac{A_0}{B_0}+\frac{A_1}{B_1}=\frac{A_0B_1+A_1B_0}{B_0B_1} \]用分治 NTT 直接维护出 \(A,B\) 就可以做了。
把这个算法转置一下，成啥样了呢？
注意一下所谓转置一定不要把不是输入输出的哪些东西转置了，也就是说常量运算不要转置。这个“常量”肯定不是一般讲的一个数，跟输入无关的多项式也要不转。比如说这个题中分母就是常量，你不要把预处理分母以及分母求逆的地方也转置了！
那么转置之后就变成了一个反着的分治，每次把多项式往底层递归而不是往上合并计算就可以了。注意这个过程中的多项式乘法是转置多项式乘法。
代码正在努力实现中。
标签：转置,多项式,pmatrix,多点,求值,vdots From： https://www.cnblogs.com/yyyyxh/p/multipoint-eval-interpolation.html