论线性算法的关系：分式分解、基变换与偏序集
飞雨烟雁
·
·
算法·理论
一、从快速插值讲起
1.「求逆原理」
习见的快速插值算法是利用 Lagrange 插值法 + 多点求值 + 分治解决的。考虑到多点求值和快速插值是两个互逆的算法。既然我们有「转置原理」，那能不能考虑弄一个「求逆原理」来改写算法呢？
事实上，我们并不能通过机械地改写某个算法，得到它的逆算法。其中一个原因是，我们需将临时变量置 0，但置 0 是不可逆的。不过，我们仍可以利用这种「求逆」的思想，将多点求值改写为快速插值算法。
下面，我们以多点求值的分治取模写法为例。暂设：
Q_{l,r}=\prod_{i=l}^r(x-x_i)
在每层递归时，我们需要分别计算 L=F\bmod Q_{l,m} 和 R=F\bmod Q_{m+1,r}。信息从 F 流向 L,R。那我们要考虑的是让信息从 L,R 流向 F，即解下面这个方程组：
\begin{cases}F\equiv L\pmod {Q_{l,m}}\\F\equiv R\pmod {Q_{m+1,r}}\end{cases}
根据 CRT，关键在于求出 Q_{l,m},Q_{m+1,r} 模对方的逆元。直接套用 HALF-GCD 算法可得 \Theta(n\log ^3n) 的快速插值算法。或根据 Q 的定义做细致的分析，应该可以做到 \Theta(n\log ^2n)。
那多点求值的转置原理写法能不能按这样改写呢？
这似乎比上面这种做法困难得多，各位可以试试看。
2. 逆转逆
另外一种思路则是考察快速插值的转置。快速插值可以写为：
f_k=[x^k]\sum_{i}a_i\prod_{j\neq i}\dfrac{x-x_j}{x_i-x_j}
其转置为：
f_k=\sum_{i}a_i[x^i]\prod_{j\neq k}\dfrac{x-x_j}{x_k-x_j}
记 A_r=\sum_i a_ix^{n-i}，可以化成：
\sum_k f_ky^k=[x^n]A_r\sum _ ky^k\prod_{j\neq k}\dfrac{x-x_j}{x_k-x_j}
看起来很不好处理。
我们转化一下思路：考察快速插值的逆的转置的逆。
这是因为，对于可逆的线性算法（即可逆矩阵）A，总有 \left((A^{-1})^T\right)^{-1}=A^T，所以快速插值的逆的转置的逆就是快速插值的转置。
而快速插值的逆的转置是一个经典问题。即在如下的定义中，给定 f_{0\sim n}，求出 g_{0\sim n}（视 x_i 为常量）。
\sum_{k}g_kx^k\equiv\sum_{k}\dfrac {f_k}{1-x_kx}\pmod {x^{n+1}}
那它的逆就是给定 g_{0\sim n}，求出 f_{0\sim n}。这是经典的分式分解，只不过分式的指数均是一次的。因此无须上分式分解，只需多点求值，设：
G(x)=\sum_{k=0}^n g_kx^k
P(x)=\prod_k{(1-x_kx)}
那么有：
{\color{red}{\left(G(x)P(x)\right)\bmod x^{n+1}}}=\sum_k f_k\prod_{j\neq k}(1-x_jx)
设红色部分为 H(x)，则：
H\left(\frac 1{x_k}\right)=f_k\prod_{j\neq k}\left(1-\frac {x_j}{x_k}\right)
因此求 f_{0\sim n} 的流程为：
-
-
对 G 做多点求值 \{x_0^{-1},x_1^{-1},\cdots ,x_n^{-1}\}；
-
它的转置就是：
-
-
-
看起来像是个新算法，但其实只需稍加变换，这个算法与旧算法并无二致。换个角度讲，在没有借助 Lagrange 插值的情况下，我们用求逆的思想导出了同一个算法。
3. 启发
我们能从上面这些内容中获得什么启发呢？首先，启发我们的是「求逆」的思想，尽管很多时候求逆并不是件简单的事。其次，转置算法的逆算法是逆算法的转置算法。当一个问题的直接转置不好处理时，我们可以考虑其逆算法的转置的逆，说不定就有意想不到的收获。
这里，我们称可逆线性算法 A 的转置算法的逆算法 A^{-T} 为反置算法，并画出如下的线性算法关系图：
\begin{aligned}
&\text{原算法}\ \ \iff\ \ \text{逆算法}\\
&\quad\Updownarrow\qquad\qquad\qquad\ \Updownarrow\\
&\!\!\!\text{转置算法}\iff\text{反置算法}\\
\end{aligned}
若视多点求值为原算法，我们就有这么一张线性算法关系图：
\begin{aligned}
&\text{多点求值}\ \iff\quad\text{快速插值}\\
&\quad\ \ \Updownarrow\qquad\qquad\qquad\quad\ \ \Updownarrow\\
&\text{分式分治}\ \iff\text{单次分式分解}\\
\end{aligned}
注：「单次分式分解」是指数均为 1 次的分式分解。
二、各种经典线性算法的关系
1. 特殊多项式复合
这里我们主要讲右复合 x+1,\frac x{1-x} 的情况。至于 e^x，大伙都很熟悉，就不讲了。
[x^k]F(x+1)&=\sum_{i}f_i[x^k](x+1)^i\\
&=\sum_i f_i\binom ik
\end{aligned}
于是复合 x+1 的转置就是二项式卷积。又因为 x+1 的逆是 x-1，所以复合 x-1 的转置就是二项式反演。
&=\sum_{i}f_i\binom{k}{i-1}\\
\end{aligned}
可以看到，复合 \frac x{1-x} 几乎就是做二项式卷积。同样可知，复合 \frac {x}{1+x} 几乎就是做二项式反演。
以下是它们的线性算法关系图：
\begin{aligned}
&\ \ \, F(x+1)\ \ \iff\ \, F(x-1)\\
&\qquad\ \Updownarrow\qquad\qquad\qquad\quad\Updownarrow\\
&F\left(\frac{x}{1-x}\right)\iff F\left(\frac{x}{1+x}\right)\\
\end{aligned}
2. 多项式复合
给定 n 次多项式 F,G，试求出 F(G(x)) 的 0\sim n 项系数。保证 g_0=0,g_1\neq 0。
注：这里的 g_0=0,g_1\neq 0 是为了保证算法可逆。
把多项式复合写成矩阵乘法的形式：
a_k=\sum_{i}f_i[x^k]G^i
\vec a=\vec f M
其中 M=\left([x^j]G^i\right)，那么它的转置（\vec b=\vec f M^T）就是：
b_k=\sum_{i}f_i[x^i]G^k
继续推导下去可得 b_k=[x^ny^k]\frac{F_r(x)}{1-yG(x)}，再用 Bostan-Mori 算法求解。故多项式复合可在 \Theta(n\log ^2n) 时间内解决。
而多项式复合的逆算法是给定 H(x)=F(G(x)) 和 G(x)，求 F(x)。这等价于求 H(G^{\left<-1\right>}(x))，比目前常说的多项式复合逆要强。
Alpha1022 提示到，直接利用另类 Lagrange 反演，有：
[x^k]H(G^{\left<-1\right>}(x))=[x^n]HG'(x/G)^{n+1}G^{n-k}
设 T(x)=HG'(x/G)^{n+1}，我们要求 [x^n]TG^k，上 Bostan-Mori 算法即可。
至于多项式的反置算法，有两种推导方法。
一个方向是考察 [x^n]\frac{F_r(x)}{1-yG(x)} 的逆算法，即给定 b_{0\sim n}，求出 f_{0\sim n}。那么我们能不能深究 Bostan-Mori 算法的过程，通过「求逆」的思想给出多项式复合的反置算法呢？也许可以，但我推不出来。
另一个方向是考察 H(G^{\left<-1\right>}(x)) 的转置算法。通过和上面类似的推导可知，多项式复合的反置算法是求 [x^n]\frac {H_r(x)}{1-yG^{\left<-1\right>}(x)}，或换元为 [G^n]\frac {H_r(G)}{1-xy}，但这看起来也很不好做。
总之，若视多项式复合为原算法，我们有以下的线性算法关系图：
\begin{aligned}
&\qquad \! F(G(x))\quad\!\iff\ H(G^{\left<-1\right>}(x))\\
&\qquad\quad\Updownarrow\qquad\qquad\qquad\qquad\ \Updownarrow\\
&[x^n]\frac{F_r(x)}{1-yG(x)}\ \!\iff \ [G^n]\frac {H_r(G)}{1-xy}\\
\end{aligned}
3. Dirichlet 前缀和
给定序列 f_1,f_2,\cdots, f_n，定义 \displaystyle g_n=\sum_{d|n}f_d，试求出 g_1,g_2,\cdots ,g_n。
我们先将其写为线性算法的形式：
\vec f=\vec g M
其中 M=([i|j])，那么它的转置就是 Dirichlet 后缀和。根据莫比乌斯反演，我们能给出其逆矩阵：M^{-1}=(\mu( j/i))。
现在我们考虑其反置算法，仍然有两个方向。第一个方向是莫反的转置，它给出了这样一个式子：
g_n=\sum_{k}f_k\mu(k/n)=\sum_{d}f_{nd}\mu(d)
另一个方向是后缀和的逆算法，利用倍数形式的莫比乌斯反演，我们可以导出同一个式子。换句话说，所谓倍数形式的莫反，与因数形式的莫反实为转置关系。
视 Dirichlet 前缀和为原算法，我们有如下的线性算法关系图：
\begin{aligned}
&\text{Dirichlet 前缀和}\ \iff\text{因数形式的莫反}\\
&\qquad\quad\Updownarrow\qquad\qquad\qquad\qquad\quad\ \ \Updownarrow\\
&\text{Dirichlet 后缀和}\ \iff\text{倍数形式的莫反}\\
\end{aligned}
4. 普通幂转下降幂
设 n 次多项式 \displaystyle F(x)=\sum_{k=0}^nf_kx^k=\sum_{k=0}^n g_kx^{\underline k}，给定 f_{0\sim n}，求 g_{0\sim n}。
先看下降幂转普通幂，因为它的推导比较直观。
f_k=\sum_{i}g_i[x^k]x^{\underline i}
其转置为：
&=\sum_{i}g_i[x^i] (1+y)^x\\
&=\sum_{i,k}g_i[x^i] \dfrac{x^k\ln^k(1+y)}{k!}\\
&=\sum_{i}\dfrac{g_i}{i!}\ln^i(1+y)\\
\end{aligned}
故下降幂转普通幂的转置就是复合 \ln(1+x)，于是普通幂转下降幂的转置就是复合 e^x-1，直接得到如下线性算法关系图：
\begin{aligned}
&\text{普通幂转下降幂}\iff\text{下降幂转普通幂}\\
&\qquad\quad\Updownarrow\qquad\qquad\qquad\qquad\quad\Updownarrow\\
&\quad\ \ F(e^x-1)\quad\ \iff\quad\! F(\ln(1+x))\\
\end{aligned}
5. 特殊多项式的基变换
给定一组模 x^{n+1} 意义下构成基底的多项式 \{\varphi_0,\varphi_1,\cdots,\varphi_n\} 及 n 次多项式 F(x)，试求系数 h_{0\sim n} 使得 F(x)=\sum_i h_i\varphi_i\bmod x^{n+1}。
比如上文那个下降幂的例子，就是一种基变换。我们这里希望考虑一些特殊多项式的基变换。首先，定义如下二元生成函数：
M(x,y)=\sum_k\varphi_k(x)\dfrac{y^k}{k!}
对于特殊多项式转回普通幂的做法：
f_k=\sum_{i}h_i[x^k]\varphi_i
转置一下，建立 EGF：
\sum_{k}g_k\frac{y^k}{k!}=\sum_{i}h_i[x^i]M(x,y)\tag{1}
接着，我们看一些具体的例子。
首先是伯努利多项式，它有如下生成函数：
M(x,y)=\sum_{k}B_k(x)\dfrac{y^k}{k!}=\dfrac{y}{e^y-1}e^{xy}
代入到 (1) 式之中：
&=\dfrac{y}{e^y-1}\sum_{i}h_i[x^i]e^{xy}\\
&=\dfrac{y}{e^y-1}\sum_{i}h_i\dfrac{y^i}{i!}\\
\end{aligned}
根据转置原理，我们可以写出伯努利多项式转普通幂的流程：
-
h_i\leftarrow h_i/i!
-
H\leftarrow H\times ^T\! \dfrac{x}{e^x-1}
-
h_i\leftarrow h_i\times i!
把流程逆过来就是普通幂转伯努利多项式的算法了。
再来一个例子，Hermite 多项式。它的一种定义是：
H_n=(-1)^n e^{x^2}\dfrac{\text d}{\text dx^n}\left(e^{-x^2}\right)
我们还是希望找到其生成函数。我不知道正常是怎么做的，这里的方法是我自己想的。
在定义式两端求导，我们得知它有如下微分迭代式：
H_{n+1}=2xH_n-H'_ n
然后用我前几天专门发的一个方法，计算可得：
\sum_nH_n(x)\dfrac{y^n}{n!}=\exp(2xy-y^2)
步骤很显然就出来了。
再来一个例子，Mott 多项式。这里直接用 Wolfram MathWorld 的结论：
\sum_n s_n(x)\dfrac{y^n}{n!}=\exp\left(x\dfrac{1-\sqrt{1+t^2}}{t}\right)
于是我们需要复合 (1-\sqrt{1+t^2})/t。这看起来有点怪，但它的反函数是 \frac{2x}{x^2-1}，可以 \Theta(n\log n) 复合。把步骤反过来就是复合 (1-\sqrt{1+t^2})/t 的方法了。
还有很多特殊多项式，大家可以在这里查看。另外，一篇 08 年的论文对这方面做了更详细的阐述。
三、分式分解与 Hermite 插值
1. 分式分解的关系图
这是分式分解：
给定 a_i,k_i(1\le i\le m) 以及一个低于 n=\sum(k_i+1) 次的多项式 F(x)，试求 R_i(x)(1\le i\le m)，满足 \deg R_i\le k_i 及下式：
\frac {F(x)}{\prod_{i=1}^m(1-a_ix)^{k_i+1}}=\sum_{i=1}^m\dfrac{R_i(x)}{(1-a_ix)^{k_i+1}}
我们上面已经讨论了 k_i\equiv 0 的情况。下面我们看一下，一般情况下的分式分解，其转置算法是什么？
直接转置似乎比较困难，我们采用「逆转逆」的思路。
分式分解的逆算法就是分治维护分式，即：
a_k&=\sum_{i}[x^k]\frac{R_i(x)}{(1-a_ix)^{k_i+1}}\\
&=\sum_{i,t}r_{i,t}[x^{k-t}]\frac{1}{(1-a_ix)^{k_i+1}}\\
&=\sum_{i,t}r_{i,t}a^{k-t}_ i\binom{k-t+k_i}{k_i}\\
\end{aligned}
方便起见，我们把 r_{i,t} 压成一维的，即用一个数列 f_k 来存储 r_{i,t} 的值。存储法则是：
\{f_0,f_1,\cdots,f_{n-1}\}=\{r_{1,0},r_{1,1},\cdots,r_{1,k_1},r_{2,0},\cdots,r_{2,k_2},\cdots ,r_{m,k_m}\}
我们设 f_k 对应的 r 为 r_{u(k),v(k)}，则有：
a_k&=\sum_{i}r_{u(i),v(i)}a^{k-v(i)}_ {u(i)}\binom{k-v(i)+k_{u(i)}}{k_{u(i)}}\\
&=\sum_{i}f_ia^{k-v(i)}_ {u(i)}\binom{k-v(i)+k_{u(i)}}{k_{u(i)}}\\
\end{aligned}
转置一下：
b_k
&=\sum_{i}f_ia^{i-v(k)}_ {u(k)}\binom{i-v(k)+k_{u(k)}}{k_{u(k)}}\\
&=\frac{1}{k_{u(k)}!}\frac {\text d^{k_{u(k)}}}{\text dx^{k_{u(k)}}}\left(x^{k_{u(k)}-v(k)}F(x)\right)\bigg|_ {x=a_{u(k)}}
\end{aligned}
于是我们可以写出分式分解的反置算法：
给定一个低于 n 次多项式 F(x) 以及 a_i,k_i(1\le i\le m)，满足 n=\sum(k_i+1)。对于 1\le i\le m,0\le j\le k_i，试求出 x^jF(x) 的 k_i 阶导在 x=a_i 处的取值。
这个形式可能不那么直观，幸好我们可以在 \Theta(k_i\log k_i) 的时间内，把 x^jF(x) 的 k_i 阶导在 x=a_i 处的取值，转化为 F(x) 的 j 阶导在 x=a_i 处的取值。具体如下，设：
c_j=\frac{\text d^{k_i}}{\text dx^{k_i}}\left(x^j F(x)\right)\Big|_ {x=a_i}
d_j=\binom {k_i}{j}F^{(k_i-j)}(a_i)
那么根据 Leibniz 公式，有：
&=j!\sum_td_t\dfrac{a_i^{j-t}}{(j-t)!}
\end{aligned}
即知 d_t 的 OGF 等于 c_j 的 EGF 卷上 \exp (-a_ix)，故可以在 \Theta(k_i\log k_i) 时间内互化。
于是我们可以在 \mathcal O(n\log n) 时间内，将这个分式分解的反置算法转化为：
给定一个低于 n 次多项式 F(x) 以及 a_i,k_i(1\le i\le m)，满足 n=\sum(k_i+1)。对于 1\le i\le m,0\le j\le k_i，试求出 F^{(j)}(a_i) 的值。
这个问题的逆算法就是一种特殊的插值。经 NaCly_Fish 提醒，这种插值就是 Hermite 插值。那么，我们不妨这个问题为 Hermite 多点求值。
综上，我们有以下线性算法关系图：
\begin{aligned}
&\text{Hermite 多点求值}\iff\text{Hermite 插值}\\
&\qquad\quad\ \,\Updownarrow\qquad\qquad\qquad\qquad\quad\Updownarrow\\
&\quad \text{分治维护分式}\;\,\;\iff\quad\!\text{分式分解}\\
\end{aligned}
（注：它们并非是严格的转置关系）
2. 分式分解新算法
受 NaCly_Fish 提到的 Hermite 插值的启发，我们可以得到一种新的分式分解算法。这里，我们先看 Hermite 多点求值。
上面的推导告诉我们，分治维护分式的转置算法，配合上 \Theta(k_i\log k_i) 的转化，就是 Hermite 多点求值。因此，我们现在可以在 \Theta(n\log ^2n) 时间内做 Hermite 多点求值。
下面，我们看 Hermite 插值。
给定 a_i,k_i(1\le i\le m)，记 n=\sum(k_i+1)，已知存在一低于 n 次的多项式 F(x)。且对于 1\le i\le m,0\le j\le k_i，给定 F^{(j)}(a_i) 的值 g_{i,j}，试求 F(x) 的系数。
先设：
Q(x)=\prod_{i=1}^m (x-a_i)^{k_i+1}
Q_i(x)=Q(x)/ (x-a_i)^{k_i+1}
类比于 Lagrange 插值，对于每个 i，我们希望找到一个多项式 L_{i}(x)：
F(x)=\sum_{i}L_i(x)Q_i(x)
那么 L_i 应当有以下性质：
\frac{\text d^j}{\text d x^j}\left(L_{i}Q_i\right)\bigg|_ {x=a_ i}=g_{i,j}
由 Taylor 公式：
L_i(x+a_i)Q_i(x+a_i)\equiv\sum_{j}\dfrac{g_{i,j}}{j!}x^j\pmod {x^{k_i+1}}
关键在于求出 Q_i(x+a_i) 各项系数的值，即求 Q_i(x) 各阶导在 x=a_i 处的取值。
此处不宜直接套用 Hermite 多点求值，我们还是用 Leibniz 公式：
Q(x)=Q_i(x)(x-a_i)^{k_i+1}
&=\binom{k_i+t+1}{k_i+1}Q_i^{(t)}(a_i)(k_i+1)!\qquad \forall \ 0\le i\le k_i\\
\end{aligned}
所以我们只需对 Q'(x) 做 Hermite 多点求值即可。注意这里最高会涉及到 2k_i 阶导，应将 Q'(x) 的次数翻倍处理。
求出 Q_i(x+a_i) 后，我们做多项式求逆，乘上 g_{i,j} 的 EGF 就是 L_i(x+a_i) 了，最后平移一下即可。
得到 L_i 后利用分治，在 \Theta(n\log ^2n) 的时间内得以解决。
综上，Hermite 插值问题得到较完满的解答。
现在考虑分式分解的转置，它并不完全等价于 Hermite 插值。但我们提过，可以在 \mathcal O(n\log n) 时间内将其转化为 Hermite 插值。因此，我们只需把这个转化操作和 Hermite 插值一起转置，就可以得到分式分解的新算法了。
新的算法有以下优点：
-
不需要写多项式取模
-
常数可能有轻微提升
Remark：如果不想用转置原理的话，似乎可以用这里面的某些步骤去替换原有的分式分解算法的一些步骤，从而规避取模。
四、再谈转置原理
1. 基变换
线性算法的本质都是在做基变换，比如多项式复合算法就是将 \{G^0,G^1,\cdots,G^n\} 基下的向量转化到 \{x^0,x^1,\cdots,x^n\} 基下的向量。那它的逆算法很好理解，就是从后一组基转化到前一组基。
那转置算法所对应的基变换是什么呢？这里需要引入一些线性代数的概念。
-
对偶空间：现有一数域 \mathbb F 上的线性空间 V，定义它的对偶空间 V^ * 为所有 V 到 \mathbb F 的线性映射构成的集合。
-
对偶基：线性空间 V 有基 \{\alpha_1,\cdots,\alpha_n\}，定义 V^* 上对应的对偶基为 \alpha^* _ i:\sum k_i\alpha_i\rightarrow k_i。
那么我们有以下结论：
如果映射 \varphi 是从基 \{\alpha_1,\cdots,\alpha_n\} 到基 \{\beta_1,\cdots,\beta_n\} 的变换，则 \varphi^T 是从基 \{\beta^* _ 1,\cdots,\beta^* _ n\} 到基 \{\alpha^* _ 1,\cdots,\alpha^* _ n\} 的变换。
所以，多项式复合的转置，其实是从基 \{[x^0],[x^1],\cdots,[x^n]\} 到基 \{[G^0],[G^1],\cdots,[G^n]\} 的变换。
此外，我们上面提到了一些特殊多项式的基变换。在某些基底下，有一些操作意外地简便。例如 \{x^i\} 基下的乘法很简便，而 \{x^{\underline i}\} 基下的求 0\sim n 点值也十分方便。那是否可以充分挖掘各种基下的简便操作，辅以基变换，快速解决某些问题呢？
2. 偏序集的转置卷积
我们上面举例线性算法时，提到了二项式反演和莫比乌斯反演，这引导我们进一步将「一般偏序集上的莫比乌斯反演」和「转置原理」的结合在一起。
上下限均存在的局部有限偏序集 (X,\le ) 上自然定义了卷积：
(f* g)(x,y)=\begin{cases}\displaystyle \sum _ {x\le z\le y}f(x,z)g(z,y)&x\le y\\ 0&x\not\le y\end{cases}
转置一下：
(f*^T g)(x,y)=\begin{cases}\displaystyle \sum _ {y\le z}f(x,z)g(y,z)&x\le y\\ 0&x\not\le y\end{cases}
其本质仍然是矩阵乘法的转置：A* B=AB^ T。
同时它给出了 dirichlet 卷积的转置：
(f*^T g)(n)=\sum_{d\ge 1}f(nd)g(d)
通过这些简单的介绍，我希望转置原理能够被应用到数论领域中，发掘更多神奇的应用。