分式分解：Transpose Free 最后更新于 2025-05-01 19:58:48

在今年 4 月份发表的[「论线性算法的关系」](https://www.luogu.com.cn/article/ft2eejw9)一文中，我提到了分式分解的新算法，但却迟迟没有给出完整的算法步骤。这主要有两个原因。一是推导过程涉及多次转置，算法细节极多；二是最后需要求 $2$ 倍长的点值，影响了算法的常数。 不过，我现已掌握了一种全新的推导方法。它可以在**不直接应用转置原理**的前提下，导出**和转置原理一样的结果**。为了更好地阐明这一方法，我们有必要先回看一个经典问题——多项式多点求值。 **前置芝士**：[多项式取模的转置写法](https://www.luogu.com.cn/article/vm1enwdo)。 ------------ 众所周知，多点求值有一种写法是分治取模。即令： $$Q_{l,r}(x)=\prod_{i=l}^r (x-a_i)\\ P_{l,r}(x)=F(x)\bmod Q_{l,r}(x)$$ 则有如下分治过程（记 $mid = \lfloor\frac{l+r}{2}\rfloor$）： $$P_{l,mid}=P_{l,r}\bmod Q_{l,mid}$$ $$P_{mid+1,r}=P_{l,r}\bmod Q_{mid+1,r}$$ 最后答案就是 $F(a_i)=P_{i,i}$。 因为每次做多项式取模时都要求一次逆，所以这个算法常数较大。不过，利用[多项式取模的转置写法](https://www.luogu.com.cn/article/vm1enwdo)，我们可以规避求逆。 方便起见，我们用线段树的语言来描述。设我们在节点 $[l,r]$ 求得 $P_{l,r}$（即获取父节点的 $P_{\text{fa}}$，并做取模）。其详细过程如下（此处用 $\tilde F$ 表示 $F$ 的系数翻转）： 1. $P_{l,r}=P_{\text{fa}}* ^{\mathsf T} \tilde Q^{-1}_ {l,r}$； 2. 截取 $P_{l,r}$ 的前若干项； 3. $P_{l,r}=P_{l,r}* ^{\mathsf T} \tilde Q_ {l,r}$。 同样地，我们可以写出节点 $[l,mid]$ 的详细过程： 1. $P_{l,mid}=P_{l,r}* ^{\mathsf T} \tilde Q^{-1}_ {l,mid}$； 2. 截取 $P_{l,mid}$ 的前若干项； 3. $P_{l,mid}=P_{l,mid}* ^{\mathsf T} \tilde Q_ {l,mid}$。 可以发现，因为矩阵乘法满足 $A^{\mathsf T}B^{\mathsf T}=(BA)^{\mathsf T}$，所以节点 $[l,r]$ 的第三步可以和节点 $[l,m]$ 的第一步做合并。变为 $P_{l,mid}=P_{l,r}* ^{\mathsf T} \tilde Q_ {mid+1,r}$。 这样就没有求逆了！ 也就是说如果节点 $[l,r]$ 有父节点，那么 $[l,r]$ 的第一步可以和父节点的第三步做合并，从而规避求逆。当然，因为根节点没有父节点，所以一开始的求逆是无法规避掉的。 通过将父节点的最后一步与本节点的第一步做合并，我们实际上将「分治取模写法」转化为了「转置原理写法」。这种合并很像是化学里的缩聚反应，故我称之为「缩聚」。 ------------ 接着看分式分解。根据 EI 的[分式分解](https://www.luogu.com/article/httwuxsz)方法，我们知道，要求得下式里的 $R_i$，关键在于求出 $P(x)\bmod (1-a_ix)^{k_i}$ 和 $Q(x)/(1-a_ix)^{k_i}\bmod (1-a_ix)^{k_i}$。 $$\dfrac{P(x)}{Q(x)}=\sum_{i=1}^{m}\dfrac{R_i(x)}{(1-a_ix)^{k_i}}\quad \deg R_i<k_i$$ 记 $q_i(x)=(1-a_ix)^{k_i}$，则 $P\bmod q_i$ 和 $Q/q_i\bmod q_i$ 均可以通过分治取模解决。那么它们同样可以进行「缩聚」。$P\bmod q_i$ 的缩聚过程与上文几乎一致。下面我们主要看 $Q/q_i\bmod q_i$ 的缩聚过程。 重新定义 $Q_{l,r}(x)=\prod_{i=l}^r q_i(x),P_{l,r}(x)=Q(x)/Q_{l,r}(x) \bmod Q_{l,r}(x)$。则 $P_{1,n}=1$，且有以下分治过程： $$P_{l,mid}=(P_{l,r}Q_{mid+1,r})\bmod Q_{l,mid}$$ $$P_{mid+1,r}=(P_{l,r}Q_{l,mid})\bmod Q_{mid+1,r}$$ 同样地，我们写出在节点 $[l,r]$ 求出 $P_{l,r}$ 的过程： 1. $P_{l,r}=P_{\text{fa}}* Q_{\text{another}}$； 2. $P_{l,r}=P_{l,r}* ^{\mathsf T} \tilde Q^{-1}_ {l,r}$； 3. 截取 $P_{l,r}$ 的前若干项； 4. $P_{l,r}=P_{l,r}* ^{\mathsf T} \tilde Q_{l,r}$。 还有在节点 $[l,mid]$ 求出 $P_{l,mid}$ 的过程： 1. $P_{l,mid}=P_{l,r}* Q_{mid+1,r}$； 2. $P_{l,mid}=P_{l,mid}* ^{\mathsf T} \tilde Q^{-1}_ {l,mid}$； 3. 截取 $P_{l,mid}$ 的前若干项； 4. $P_{l,mid}=P_{l,mid}* ^{\mathsf T} \tilde Q_{l,mid}$。 我们关注节点 $[l,r]$ 的第四步和节点 $[l,mid]$ 的前两步，尝试将其合并。用 `reverse` 表示系数翻转操作，我们把这三步的涉及的转置卷积展开： 1. $\text{reverse } P_{l,r}$； 2. $P_{l,r}=P_{l,r}* \tilde Q_{l,r}$； 3. $\text{reverse }P_{l,r }$； 4. $P_{l,mid}=P_{l,r}* Q_{mid +1,r}$； 5. $\text{reverse }P_{l,mid}$； 6. $P_{l,mid}=P_{l,mid}* \tilde Q^{-1}_ {l,mid}$； 7. $\text{reverse }P_{l,mid}$。 接着将第三、四、五步合并为 $P_{l,mid}=P_{l,r}* \tilde Q_{mid + 1,r}$： 1. $\text{reverse } P_{l,r}$； 2. $P_{l,r}=P_{l,r}* \tilde Q_{l,r}$； 3. $P_{l,mid}=P_{l,r}* \tilde Q_{mid +1,r}$； 4. $P_{l,mid}=P_{l,mid}* \tilde Q^{-1}_ {l,mid}$； 5. $\text{reverse }P_{l,mid}$。 然后合并第二、三、四步： 1. $\text{reverse } P_{l,r}$； 2. $P_{l,mid}=P_{l,r}* \tilde Q^{2}_ {mid+1,r}$； 3. $\text{reverse }P_{l,mid}$。 可以发现这就是 $P_{l,mid}=P_{l,mid}* ^{\mathsf T}\tilde Q^2_{mid+1,r}$，缩聚结束。 不过，还有些边界问题需要处理。因为叶子节点没有子节点，所以它的最后一步没法做化简。另一方面，因为根节点 $[1,n]$ 的 $P_{1,n}=1$，无需按分治的过程求解，这导致了其子节点 $[1,n/2],[n/2+1,n]$ 的前两步无法参与缩聚。 我们有两种方法来解决这个问题。一是对这两个节点放弃缩聚，按原本的步骤去进行。二是给根节点补上第四步操作，即令 $P_{1,n}=P_{1,n}* ^{\mathsf T} \tilde Q^{-1}_ {1,n}$，这样后续节点就可以缩聚了。 求出 $P\bmod q_i$ 和 $Q/q_i\bmod q_i$ 之后，按 EI 里面讲的继续做即可。常数相较于原做法有较大提升。 ------------ 但是，我们凭什么认为这样得到的新算法和转置原理得出的算法是一样的呢？ 这是因为，该算法与转置原理的算法有诸多相似之处。例如求 $Q/q_i\bmod q_i$ 的主要过程是与 $ \tilde Q^2_{l,r}$ 做转置卷积，这对应着原先转置原理算法里的求两倍长的点值；再比如最后求 $(Q/q_i\bmod q_i)^{-1}\bmod q_i$ 的过程，对应着转置算法中用 Leibniz 公式做的变换…… 众多相似点都说明了，我们可以利用缩聚，得出和转置原理一样的算法。 另外，[hly1204](https://www.luogu.com.cn/user/242973) 提到，多项式取模的转置写法可以不依赖于转置原理导出（类似于 [Blog 1](https://loj.ac/d/3626), [Blog 2](https://hly1204.blog.uoj.ac/blog/9207)）。因此，我们可以这样说：**无需任何转置原理的内容，我们依旧可以得到同个多点求值、分式分解算法。** 至于代码什么的，先咕着，有时间一定来写（