P4512 题解 / 神奇的多项式取模恒等式

· · 题解

在初学多项式除法之时，我曾惊叹于其中巧妙的系数翻转操作。两年过去了，初时的震撼已褪为另辟蹊径的渴望。回看此题，我又有了不同的想法——转置原理。它总会给问题带来全新的解法，并揭示更深层次的关联。

好，闲话结束，我们进入正题。

约定：对于任意的大写字母（比如 A），我们用对应的小写字母数列 a_k 表示 [x^k]A(x)。并用下标 r 表示系数翻转，例如 F(x)=1+2x,F_r(x)=2+x。

设 R(x)=F(x)\bmod G(x),n=\deg F,m=\deg G，则有：

r_k=\sum_{i=0}^n f_i [x^k](x^i\bmod G(x))

转置一下：

&=\sum_{i=0}^n [x^{n-i}]F_r(x) [x^i](x^k\bmod G(x))\\ &=[x^{n}]F_r(x) (x^k\bmod G(x))\\ \end{aligned}

但是这个要怎么解决呢？要注意「先取模后乘法」和「先乘法后取模」是不一样的，我们并不能将其化为 (x^kF(x))\bmod G(x)。但是，借助下面这个公式，我们可以实现完美的转化。

对于任意的自然数 k，我们恒有：

[x^{n}]F_r(x)(x^k\bmod G(x))=[x^k]\dfrac{(F(x)G_r(x))\bmod x^{m}}{G_r(x)}

嗯？！这个等式是怎么来的？

事实上，这个等式的左端描述的是用 Fiduccia 算法求解「常系数齐次线性递推」，右端描述的是用 LSB-First 算法求解「常系数齐次线性递推」。这样看来，这个式子是很直观的。

这么美妙的式子理应有种美妙的证法。可是我没能想到，暂且提供一个简单的归纳证明。

先凑出 $G(x)$ 的形式： $$\sum_{i=0}^m g_{m-i}[x^n]F_r(x)(x^{k-i}\bmod G(x))=[x^n]F_r(x)(x^{k-m}G(x)\bmod G(x))=0$$ 故有： $$\begin{aligned}[x^n]F_r(x)(x^k\bmod G(x))&=-\frac 1{g_m}\left(\sum_{i=1}^m g_{m-i}[x^n]F_r(x)(x^{k-i}\bmod G(x))\right)\\ &=-\frac 1{g_m}\left(\sum_{i=1}^m g_{m-i}[x^{k-i}]\dfrac{(F(x)G_r(x))\bmod x^{m}}{G_r(x)}\right)\\ &=-\frac 1{g_m}\left( [x^{k}]G_r(x)\dfrac{(F(x)G_r(x))\bmod x^{m}}{G_r(x)}-g_{m}[x^{k}]\dfrac{(F(x)G_r(x))\bmod x^{m}}{G_r(x)}\right)\\ &=[x^{k}]\dfrac{(F(x)G_r(x))\bmod x^{m}}{G_r(x)}\\ \end{aligned}$$ 综上，等式得证。 ------------ 利用该公式，我们有： $$r^{\mathsf T}_ k=[x^{k}]\dfrac{(F(x)G_r(x))\bmod x^{m}}{G_r(x)}$$ 于是有多项式取模的转置算法： 1. 卷上 $G_r$，截取前 $m$ 项； 2. 卷上 $G_r^{-1}$。 把该过程转置即得多项式取模算法： 1. $F=F*^{\mathsf T}G_r^{-1}$； 2. 截取前 $m$ 项； 3. $F=F*^{\mathsf T}G_r$。 其中 $* ^{\mathsf T}$ 表示多项式乘法的转置。 我们可以这样来理解这几个步骤：第一步相当于把 $F$ 的高次项对取模结果的贡献，累加到低次项；第二步丢弃了高次项的信息；第三步是将低次项整理为取模结果。 至于 $F=G* Q+R$ 中的 $Q$，只需在求出 $R$ 后用 $Q=(F-R)/G$ 计算即可。也可以用原先的方法计算 $Q$，或者直接算出 $Q$ 的 FFT 点值，然后再逆回去。方法有很多，但实际应用中我们更关注的是取模，而非整除。 ------------ Remark： 上面的推导过程也告诉我们，「多项式取模」和「常系数线性递推」之间存在转置关系。这个事实在 EI 的 [一种新的线性递推计算方法](https://blog.csdn.net/EI_Captain/article/details/109196620) 中亦有记载，但少有人提及。