基本原理
我们知道矩阵的转置满足如下性质：
记 \(V=E_1E_2\dots E_k\)，则 \(V^T=E_k^T\dots E_2^TE_1^T\)。
这也就相当于，如果我们有快速的方法得到出 \(V^T=E_k^T\dots E_2^TE_1^T\) 的具体过程，也就是知道每一个 \(E_i\)，我们就可以通过把这个过程完全倒过来处理来得到 \(V\)。
这就意味着，如果我们处理的某一个问题可以抽象成 \(Vf\) 的形式（其中 \(V\) 为矩阵，\(f\) 为列向量），我们便可以把处理 \(V^Tf\) 的方式机械改来处理 \(Vf\)。
我们现在要考虑将矩阵拆解成初等行变换：
- 交换两行，记为 \(x\leftrightarrow y\)。
- 将某一行乘上 \(k\)，记为 \(x\gets kx\)。
- 将某一行加上另一行的 \(k\) 倍，记为 \(x\gets x+ky\)。
通过列出这些变换的矩阵，可以得到它们的转置矩阵是什么变换，其中 \(x\leftrightarrow y\) 和 \(x\gets kx\) 均不变，而 \(x\gets x+ky\) 则变成了 \(y\gets y+kx\)。
多项式卷积的转置
假设我们在考虑 \(V^Tf\) 的过程中，如果常量 \(A\) 与变量 \(B\) 做加法卷积得到 \(C\)，也就是 \(A\times B\to C\)，我们来考虑它的转置 \(C\times^TA\to B\)。
这个卷积过程就是 \(a_i\times b_j\to c_{i+j}\)，所以它的转置应为 \(c_{i+j}\times a_i\to b_j\)，也就是 \(c_i\times a_j\to b_{i-j}\)，加法卷积的转置就是进行一次减法卷积。
多项式多点求值。
给定多项式 \(F(x)\)，求 \(F(a_1),F(a_2)\dots F(a_m)\) 的值。
不妨将 \(F\) 的最高次项为定为 \(n\)，即 \(F(x)=\sum\limits_{i=0}^nf_ix^i\)，并将 \(a_i\) 的下标扩展至 \(a_0\sim a_n\)。
记列向量 \(f=\begin{bmatrix}f_0\\f_1\\\vdots\\f_n\end{bmatrix}\)，矩阵 \(V=\begin{bmatrix}1&a_0&a_0^2&\dots&a_0^n\\1&a_1&a_1^2&\dots&a_1^n\\ \vdots&\vdots&\vdots&\ddots&\vdots\\1&a_n&a_n^2&\dots&a_n^n\end{bmatrix}\)，我们要求的就是 \(Vf\)。
考虑问题的转置 \(V^Tf\)，也就是求 \(\begin{bmatrix}1&1&1&\dots&1\\a_0&a_1&a_2&\dots&a_n\\a_0^2&a_1^2&a_2^2&\dots&a_n^2\\ \vdots&\vdots&\vdots&\ddots&\vdots\\a_0^n&a_1^n&a_2^n&\dots&a_n^n\end{bmatrix}f\)。
不难发现，上式中要求的就是 \(\sum\limits_{i=0}^nf_ia_i^k,k=0,1,2\dots n\)，相当于求 \([x^k]\sum\limits_{i=0}^n\dfrac{f_i}{1-a_ix},k=0,1,2\dots n\)。
而求 \(\sum\limits_{i=0}^n\dfrac{f_i}{1-a_ix}\) 的过程，我们可以使用分治在 \(O(n\log^2n)\) 的时间内完成：
1.对于 \([i,i]\)，维护 \(\dfrac{P_{i,i}}{Q_{i,i}}\)，其中 \(P_{i,i}=f_i\)，\(Q_{i,i}=1-a_ix\)。
2.求解 \([l,r]\) 时，先求出 \([l,mid]\) 和 \([mid+1,r]\) 的结果 \(\dfrac{P_{l,mid}}{Q_{l,mid}}\) 和 \(\dfrac{P_{mid+1,r}}{Q_{mid+1,r}}\)。则 \(\dfrac{P_{l,r}}{Q_{l,r}}=\dfrac{P_{l,mid}}{Q_{l,mid}}+\dfrac{P_{mid+1,r}}{Q_{mid+1,r}}\) ，所以 \(P_{l,r}=P_{l,mid}\times Q_{mid+1,r}+P_{mid+1,r}\times Q_{l,mid},Q_{l,r}=Q_{l,mid}\times Q{mid+1,r}\)。
3.最终结果为 \(P_{0,n}\times Q_{0,n}^{-1}\)。
由于 \(Q\) 是与 \(f\) 无关的常量，我们来考虑 \(P\) 的线性变换过程和转置：
1.对于 \([i,i]\)， \(F(a_i)=[x^0]P_{i,i}\) 。
2.线性变换过程为 \(P_{l,r}\gets P_{l,r}+P_{l,mid}\times Q_{mid+1,r}\)，\(P_{l,r}\gets P_{l,r}+P_{mid+1,r}\times Q_{l,mid}\)。其转置为 \(P_{l,mid}\gets P_{l,mid}+P_{l,r}\times^T Q_{mid+1,r}\)，\(P_{mid+1,r}\gets P_{mid+1,r}+P_{l,r}\times^T Q_{l,mid}\)。
3.最终为 \(F\gets F+P_{0,n}\times Q_{0,n}^{-1}\)，其转置为 \(P_{0,n}\gets P_{0,n}+F\times^T Q_{0,n}^{-1}\) 。
完成上述过程，即可时间 \(O(n\log^2n)\) 多项式多点求值，由于没有大量多项式取模，常数较小。
AC记录。