转置原理 小记
Aaron_Romeo
·
·
算法·理论
多点求值
给定 n 次多项式 f(x) 和 a_0, a_1, \dots, a_{m}, 求 f(a_0), f(a_1), \dots, f(a_m)。
这就是经典的多点求值问题。我们有容易理解的 O(n \log^2n) 算法：
注意到 f(a_i) \equiv f(x) \ \text{mod} \ (x - a_i), 所以我们可以尝试求出 f(x) 对 m + 1 个单项式取模的结果。
考虑分治。把 [0, m] 均分为 [0,\dfrac{m}{2}] 和 [\dfrac{m}{2}+1, m]， 先将 f(x) 对 \prod\limits_{i = 0}^{m}(x - a_i) 取模，然后递归左右区间即可。取模复杂度 O(n\log n), 所以总复杂度为 O(n\log^2n)。
这个算法容易理解，但是取模具有极大常数，所以总效率极低。
所以我们使用更优、且理论价值更高的转置原理。
转置原理
多项式求值的本质是相当简单的：求一个向量 f 左乘范德蒙德矩阵
\mathrm{V}(a_0,\dots, a_m) =
\begin{bmatrix}
1 &\ \ a_0 &\ \ a_0^2 &\ \ \cdots &\ \ a_0^{n} \\
1 &\ \ a_1 &\ \ a_1^2 &\ \ \cdots &\ \ a_1^{n} \\
\vdots &\ \ \vdots &\ \ \vdots &\ \ \ddots &\ \ \vdots \\
1 &\ \ a_m &\ \ a_m^2 &\ \ \cdots &\ \ a_m^{n} \\
\end{bmatrix}
但不能直接求解，此时我们要另辟蹊径。发现 f 左乘矩阵 \mathrm{V} 的转置 \mathrm{V}^\mathrm{T} 是好求的：
\mathrm{V^\mathrm{T}}(a_0,\dots, a_m) =
\begin{bmatrix}
1 &\ 1 &\ \ \cdots &\ \ 1 \\
a_0 &\ \ a_1 &\ \ \cdots &\ \ a_m \\
\vdots &\ \ \vdots &\ \ \ddots &\ \ \vdots \\
a_0^{n} &\ \ a_1^{n} &\ \ \cdots &\ \ a_m^{n} \\
\end{bmatrix}
，\ \ \ \
g_i = \sum\limits_{j=0}^{m}f_{j}a_{j}^{i}
这里若 \mathrm{V} 不是方阵，无法右乘相同的向量。所以在这里认为 n = m，实际算的时候补 0 即可。
记 G(x) 为 g 的生成函数，有
G(x) = \sum\limits_{i=0}^{n}\sum\limits_{j=0}^{n}f_{j}\times(a_jx)^i
因为我们只要 G(x) 的前 n+1 项，所以他在模 x^{n+1} 的意义下也能写成
\begin{aligned}
G(x) &=
\sum\limits_{j=0}^{n}f_{j}\sum\limits_{i=0}^{n}(a_jx)^i \\
&= \sum\limits_{i=0}^{n}\dfrac{f_i}{1-a_ix} \\
&= \dfrac{\sum\limits_{i=0}^{n}f_i\prod\limits_{j=1,j\ne i}^{n}(1-a_jx)}{\prod\limits_{i=1}^{n}(1-a_ix)} \\
\end{aligned}
于是采用分治 NTT 计算，过程中维护 Q_{l,r}(x)=\prod\limits_{i=l}^{r}(1-a_ix)，时间复杂度 O(n\log^2n)。
伪代码 :
\begin{aligned}
1& &&\mathrm{Solve}(l,r) :\\
2& &&\qquad\mathrm{if}\ l = r : \mathrm{return}\ f_l \\
3& &&\qquad m\leftarrow\lfloor(l+r)/2\rfloor \\
4& &&\qquad x,y\leftarrow0 \\
5& &&\qquad L\leftarrow \mathrm{Solve}(l,m) \\
6& &&\qquad R\leftarrow \mathrm{Solve}(m + 1, r) \\
7& &&\qquad x\leftarrow x+L\times Q_{m+1, r}(x) \\
8& &&\qquad y\leftarrow y+R\times Q_{l, m}(x) \\
9& &&\qquad F\leftarrow0 \\
10& &&\qquad F\leftarrow F+x\times 1 \\
11& &&\qquad F\leftarrow F+y\times 1 \\
12& &&\qquad \mathrm{return}\ F\ \\
13& &&g\leftarrow g+\mathrm{Solve}(0,n)\times Q^{-1}_{0,n}(x) \\
\end{aligned}
观察代码后不难发现，所有操作都能写成矩阵乘法。将视角放大，整个算法能被解释为模拟矩乘。说人话：
我们把其视为 在 f 以及辅助数组 x 和 y 组成的向量上进行的矩乘。即：
f'=
\begin{bmatrix}
f_0\\
f_1\\
\vdots\\
f_n\\
x_0\\
x_1\\
\vdots\\
x_n\\
y_0\\
y_1\\
\vdots\\
y_n\\
\end{bmatrix}
对于 x,y\leftarrow0 显然能矩乘实现。
对于 x\leftarrow x+L\times Q_{m+1, r}(x)，L 就是当前的 f_{l,m}，此处可以解释为在 x 上累加 f 的线性变换，能矩乘。
对于 y\leftarrow y+R\times Q_{l, m}(x)，同上。
随后将 f_{l,r} 清空：F\leftarrow0，同上。
对于 F\leftarrow F+1\times x 和 F\leftarrow F+1\times y ，理解为将 f_{l,r} 变成 x + y，也是将线性变换累加，同上。
对于最后的 g\leftarrow g+\mathrm{Solve}(0,n)\times Q^{-1}_{0,n}(x)，即在 f_{0,n} 上的线性变换，仍然同上。
所以整个算法等价于在模拟：\mathrm{P_0\times P_1 \times \dots \times P_k} \times f'。其中观察发现所有 \mathrm{P} 都是与 f' 无关的。
这个性质有什么用呢？
已知如何求 \mathrm{V^\mathrm{T}} \times f' ，要求 \mathrm{V} \times f'。
因为 \mathrm{V^\mathrm{T}} \times f' = \mathrm{P_0\times P_1 \times \dots \times P_k} \times f'，\mathrm{P} 和 \mathrm{V^\mathrm{T}} 均与 f' 无关，所以此式对任何 f' 均成立。因此不需要 f' 有逆元就能推出 \mathrm{V^\mathrm{T}} = \mathrm{P_0\times P_1 \times \dots \times P_k}。
根据
\mathrm{A\times B=C} \Leftrightarrow \mathrm{B^\mathrm{T}}\times\mathrm{A^\mathrm{T}}=\mathrm{C^\mathrm{T}}
所以 \mathrm{V^\mathrm{T}} = \mathrm{P_0\times P_1 \times \dots \times P_k}，得 \mathrm{V} = \mathrm{P^\mathrm{T}_k\times P^\mathrm{T}_{k-1} \times \dots \times P^\mathrm{T}_0}。
问题转化为如何模拟 \mathrm{P^\mathrm{T}_k\times P^\mathrm{T}_{k-1} \times \dots \times P^\mathrm{T}_0}\times f'。我们将其分为两个部分：
-
计算乘矩阵转置
-
将计算顺序倒过来(即：将 从 \mathrm{P_0} 开始 乘到 \mathrm{P_k} 的顺序变成 从 \mathrm{P^\mathrm{T}_k} 开始 乘到 \mathrm{P^\mathrm{T}_0})。
第一部分
原函数只有赋值为 0 和累加线性变换两种计算。显然赋值为 0 的转置为自己，根本不用变，因此只用考虑累加线性变换的转置。
如下，其意义为 f_{x,y}\leftarrow f_{x,y}+f_{l,r}\times P：
注意到，除了 i\in[x,y],j\in[l,r] 里的点为 P 表示的矩阵外，其他点均满足值为 [i==j](即单位矩阵)。
其的转置为：
易得其意义为 f_{l,r}\leftarrow f_{l,r}+f_{x,y}\times^\mathrm{T} P。
下探究如何计算多项式乘法的转置：
### 加法卷积转置
若将 $H = F * G$ 中的 $F$ 看作右乘的向量，$G$ 看作左乘的矩阵，由
$$
H_k=\sum\limits_{i=0}G_{k-i}F_i，
$$
有：
$$
\mathrm{M}_{i,j}=[i\ge j]G_{i-j}
$$
可知转置后 $H'=\sum\limits_{i=k}G_{i-k}F_i=\sum\limits_{i=0}G_iF_{i+k}
即为减法卷积。
第二部分
原算法的计算顺序为后序遍历，因为要反转计算顺序，我们改为前序遍历。注意：在递归时同一层之间的计算顺序不影响答案。
直接上伪代码：
\begin{aligned}
1& &&\mathrm{Solve}(l,r,F) :\\
2& &&\qquad\mathrm{if}\ l = r : f_l \leftarrow F_0\ \mathrm{return}\\
3& &&\qquad m\leftarrow\lfloor(l+r)/2\rfloor \\
4& &&\qquad y\leftarrow y+F\times^\mathrm{T} 1 \\
5& &&\qquad x\leftarrow x+F\times^\mathrm{T} 1 \\
6& &&\qquad F\leftarrow0 \\
7& &&\qquad R\leftarrow R+y\times^\mathrm{T} Q_{l, m}(x) \\
8& &&\qquad L\leftarrow L+x\times^\mathrm{T} Q_{m+1, r}(x) \\
9& &&\qquad \mathrm{Solve}(m + 1, r, R) \\
10& &&\qquad \mathrm{Solve}(l,m, L) \\
11& &&\qquad x,y\leftarrow0 \\
12& &&\qquad \mathrm{return} \\
13& &&\mathrm{Solve}(0,n,F\times^\mathrm{T} Q^{-1}_{0,n}(x)) \\
\end{aligned}
就是将所有计算倒过来并替换成对应的转置而已，十分简单。
精简代码：
\begin{aligned}
1& &&\mathrm{Solve}(l,r,F) :\\
2& &&\qquad\mathrm{if}\ l = r : f_l \leftarrow F_0\ \mathrm{return}\\
3& &&\qquad m\leftarrow\lfloor(l+r)/2\rfloor \\
4& &&\qquad L\leftarrow L+F\times^\mathrm{T} Q_{m+1, r}(x) \\
5& &&\qquad R\leftarrow R+F\times^\mathrm{T} Q_{l, m}(x) \\
6& &&\qquad \mathrm{Solve}(l,m, L) \\
7& &&\qquad \mathrm{Solve}(m + 1, r, R) \\
8& &&\qquad \mathrm{return} \\
9& &&\mathrm{Solve}(0,n,F\times^\mathrm{T} Q^{-1}_{0,n}(x)) \\
\end{aligned}
时间复杂度显然和原算法一致，为 O(n\log^2n)。
一些理解
一般转置原理用在对每个下标要求几个 \sum 的情况，需要自己构造矩阵 \mathrm{M}_{i,j}。i 自然选的是你要求的下标，j 则选你转置之后更好求的那个下标。然后只要能构造出矩阵且转置后乘任意向量都好算还能转置回来，那就可以用转置原理。简单点说就是你把所有逻辑都说通就行了。
Example
求 b_i=\sum\limits_{j}\dfrac{|i|+|j|}{|i\ |\ j|}\times a_j
发现如果以 |i\ |\ j| 为下标的话可能可能可以用 FWT 快速求得。
于是我们先把矩阵写出来，再转置之后看到底好不好算。
很容易得矩阵 \mathrm{M}_{i,j}=\sum\limits_{k,i|k=j}\dfrac{|i|+|k|}{|j|}\times a_k，变量向量是全 1 向量。
转置后发现求的是：b'_i=\sum\limits_{j,k,j|k=i}\dfrac{|j|+|k|}{|i|}\times a_k，显然可以用 FWT 瞎√8求，然后就做完了。
例题
[USACO24DEC] All Pairs Similarity P
[GYM102978D]Do Use FFT
[湖北省选模拟 2025] 团队协作
「KrOI2021」Feux Follets
参考文章
Vocalise：《多点求值插值、转置算法以及范德蒙德矩阵逆》
command_block：《转置原理小记》