最近遇到了多点求值的题，但我还没学过经典的多项式取模版本，于是就直接学新做法了。

这个新做法其实非常容易懂，但是还是花了我太长时间（我是菜逼）

如论文里所说，这个做法的代码非常简单，都不用调多久。

这个原理是指在通过矩阵乘法进行的线性变换（如求 A x Ax Ax， x x x 是一个列向量）过程中，我们想要求得 A T x A^Tx ATx，除了可以直接把 A A A 转置过后乘上 x x x，还可以把线性变换过程中的步骤进行一些倒序和改动以达到目的。

具体地，我们把线性变换过程分为3种指令：

（其实还有第四种，就是把答案输出到数组中，但是个人认为它本质上就是第三种）

那么我们要实现变换的转置，就只需要把指令的顺序倒过来，然后把第三种指令add i j c变为add j i c。这里的乘法如果是多项式乘法或矩阵乘法的话，就要变为这种乘法运算的转置。

至于这么做为什么是对的，我不太会证（据说是用归纳法），但你应该能体会到它的正确性。

由于矩阵乘法可以拟合所有线性运算，所以我们平时用的线性算法，如二项式反演、多项式全家桶等都适用这个原理。

由于论文说傅里叶变换的转置是它本身，所以我们就跳过傅里叶，直接说多项式乘法了。

上面说了第三种指令会用到乘法转置，这也是多点求值新方法中的重要前置知识。

对于多项式乘法 f ∗ g = ∑ i = 0 n + m − 2 ( ∑ j = 0 i f j ⋅ g i − j ) x i f*g=\sum_{i=0}^{n+m-2}(\sum_{j=0}^if_j\cdot g_{i-j})x^i f∗g=∑i=0n+m−2​(∑j=0i​fj​⋅gi−j​)xi，我们把它想成向量和矩阵相乘，可以推出它的转置为 ( f ∗ g ) T = ∑ i = 0 n − m ( ∑ j = 0 m f m − 1 − j + i g m − 1 − j ) x i (f*g)^T=\sum_{i=0}^{n-m}(\sum_{j=0}^mf_{m-1-j+i}g_{m-1-j})x^i (f∗g)T=∑i=0n−m​(∑j=0m​fm−1−j+i​gm−1−j​)xi。由于与下标差有关，所以多项式乘法的转置也被叫做“减法卷积”。

看上去有点复杂，但其实它就是 f f f 与系数翻转后的 g g g 进行普通多项式乘法后的第 m − 1 m-1 m−1 到第 n − 1 n-1 n−1 项。

多项式乘法是把 n n n 次和 m m m 次变为 n + m n+m n+m 次，它的转置则是把 n + m n+m n+m 次和 m m m 次变为 n n n 次，所以它们是倒过来的，代码中要尤其注意多项式的次数。

这里不方便打矩阵，所以直接截PDF了： 我们把 ∑ j = 0 n − 1 b j 1 − a j x \sum_{j=0}^{n-1}\frac{b_j}{1-a_jx} ∑j=0n−1​1−aj​xbj​​ 通分后就变为了 b 0 ( 1 − a 1 x ) . . . ( 1 − a n − 1 x ) + ( 1 − a 0 x ) b 1 . . . ( 1 − a n − 1 x ) + . . . + ( 1 − a 0 x ) . . . ( 1 − a n − 2 x ) b n − 1 ( 1 − a 0 x ) ( 1 − a 1 x ) . . . ( 1 − a n − 1 x ) \frac{b_0(1-a_1x)...(1-a_{n-1}x)+(1-a_0x)b_1...(1-a_{n-1}x)+...+(1-a_0x)...(1-a_{n-2}x)b_{n-1}}{(1-a_0x)(1-a_1x)...(1-a_{n-1}x)} (1−a0​x)(1−a1​x)...(1−an−1​x)b0​(1−a1​x)...(1−an−1​x)+(1−a0​x)b1​...(1−an−1​x)+...+(1−a0​x)...(1−an−2​x)bn−1​​ 这个东西显然可以用线段树维护，我们在线段树上每个节点设置两个多项式 F l , r F_{l,r} Fl,r​ 和 T l , r T_{l,r} Tl,r​ 表示区间内答案的分子和分母，则我们要做的转移是 T l , r = T l , m i d ∗ T m i d + 1 , r F l , r = F l , m i d ∗ T m i d + 1 , r + F m i d + 1 , r ∗ T l , m i d T_{l,r}=T_{l,mid}*T_{mid+1,r}\\ F_{l,r}=F_{l,mid}*T_{mid+1,r}+F_{mid+1,r}*T_{l,mid} Tl,r​=Tl,mid​∗Tmid+1,r​Fl,r​=Fl,mid​∗Tmid+1,r​+Fmid+1,r​∗Tl,mid​ 特别地， F l , l = b l , T l , l = 1 − a l x F_{l,l}=b_l,T_{l,l}=1-a_lx Fl,l​=bl​,Tl,l​=1−al​x。我们最后求的就是 F 0 , n − 1 T 0 , n − 1 {F_{0,n-1}\over T_{0,n-1}} T0,n−1​F0,n−1​​，需要用一次多项式求逆。

上面的方法求的是原来的多点求值的转置，所以运用转置原理，我们把上面的计算过程转置一下就可以求出正常的多点求值。

依照规律，我们把过程倒过来，也就是线段树上从上往下递归。由于转置原理中只能有一个变量（一个向量，或者多项式），所以我们不妨正常地预先求出所有 T T T，然后把它当成常量看待，这样我们从上往下递归时的操作就是 F l , m i d ′ = ( F l , r ′ ∗ T m i d + 1 , r ) T F m i d + 1 , r ′ = ( F l , r ′ ∗ T l , m i d ) T F'_{l,mid}=(F'_{l,r}*T_{mid+1,r})^T\\ F'_{mid+1,r}=(F'_{l,r}*T_{l,mid})^T Fl,mid′​=(Fl,r′​∗Tmid+1,r​)TFmid+1,r′​=(Fl,r′​∗Tl,mid​)T 递归到最底部时， F i , i ′ F'_{i,i} Fi,i′​ 为0次，只有一个值，就是这个位置的答案。

根据原理，最顶部的 F ′ F' F′ 应该为你要进行多点求值的这个多项式和 1 T 0 , n − 1 \frac{1}{T_{0,n-1}} T0,n−1​1​ 进行“减法卷积”的结果。

但是我们求的 F F F 的次数应该是 n − 1 n-1 n−1 次的，而原多项式是 n − 1 n-1 n−1 次， T 0 , n − 1 T_{0,n-1} T0,n−1​ 是 n n n 次，直接做减法卷积显然次数对不上。

再想想，我们原过程的 F 0 , n − 1 T 0 , n − 1 {F_{0,n-1}\over T_{0,n-1}} T0,n−1​F0,n−1​​ 相当于是乘法过后去掉了 n n n 次及以后的部分，去掉这些部分相当于乘以常数0，这个指令转置过后不变，还是原位置乘以0。但是原多项式是 n − 1 n-1 n−1 次，它的 n n n 次以后本就为0，所以只需要把它的大小扩充到 2 n − 1 2n-1 2n−1 次再做减法卷积即可。

据说这个方法常数要小很多，正好弥补了vector的常数缺陷。