多项式求逆

多项式的逆

如同一般整数的乘法逆元一样，我们可以定义多项式的“逆”。对于给出的一个 $n-1$ 次多项式 $F(x)$ ，如果存在一个 $n-1$ 次多项式，使得多项式乘法的结果 $F(x)*G(x)$ 在对 $x^n$ 取模后，只有常数项1，那么就把 $G(x)$ 称为 $F(x)$ 的逆，记作

$F(x)*G(x) \equiv 1 \pmod {x^n}$

值得注意的是，多项式的取模和系数的取模是完全两码事。一个多项式可以理解成一个 $x$ 进制数。当多项式对 $x^n$ 取模时，其实就是扔掉从 $x^n$ 开始的所有高次项。即多项式的取模是为了限定项数的。

$F(x)$ 模 $x^n$ 的逆有几项呢？事实上，在多项式问题中，“几项”这个问题是不重要的，因为如果愿意，我们可以认为所有多项式都有无限项，只不过高次的系数都是0罢了。重要的是，多项式有多少项会对我们解决问题产生影响。在这个问题中，多项式的逆只有 $n$ 项对求解产生影响，所以如果模数是 $x^n$ ，我们便可以认为 $G(x)$ 与 $F(x)$ 都是 $n$ 项的多项式。

多项式的逆是唯一的吗？我们知道整数的乘法逆元是唯一的，用反证法容易证明。而多项式的乘法本质上是系数的卷积。手动代入求解一下就可以发现多项式的逆也是唯一的：由 $F_0$ 我们可以解出 $G_0$ 就是 $F_0$ 的乘法逆元，再根据方程 $F_0G_1+F_1G_0 \equiv 0 \pmod P$ 可以解得唯一的 $G_1$ 。然后不停地解出 $G_2,G_3,...$ ，所以多项式的逆是唯一的。

求解多项式的逆

我们可以给 $F(x)$ 的高次项补0使得 $n$ 为2的幂次。由于多项式的逆是唯一的，因此补0后的 $G(x)$ 就是补0后的 $F(x)$ 的逆。而补0其实相当于什么事都没干。所以我们对 $n$ 做的变换是完全没有问题的。以下假定 $n$ 为2的幂次。

假设已经求解出了对 $x^{n/2}$ 取模后 $F(x)$ 的逆 $H(x)$ ，则有

$F(x)*H(x) \equiv 1 \pmod {x^{n/2}}$

根据多项式的逆的定义，又有

$F(x)*G(x) \equiv 1 \pmod {x^{n/2}}$

因此

$F(x)*[G(x)-H(x)] \equiv 0 \pmod {x^{n/2}}$

多项式可以当作一个 $x$ 进制数来理解，因此如果两数的乘积为0，其中至少有一个数为0。而因为我们假定了 $F(x)$ 的逆是有解的，因此 $F(x)$ 不能为0，所以

$G(x)-H(x) \equiv 0 \pmod {x^{n/2}}$

也就是说 $G(x)$ 和 $H(x)$ 的前 $n/2$ 项是一模一样的。现在，我们要开始考虑前 $n$ 项的问题了。由于这个新的多项式，不妨令它为 $P(x)=G(x)-H(x)$ ，的前 $n/2$ 项都为0，我们用系数卷积思考一下就会发现， $P^2(x)$ 的前 $n-1$ 项都为0。也就是

$G^2(x)+H^2(x)-2G(x)H(x) \equiv 0 \pmod {x^n}$

至此，我们已经将模数扩大为了 $x^n$ 。我们在新的等式两边同时乘以 $F(x)$ 得

$F(x)G^2(x)+F(x)H^2(x)-2F(x)G(x)H(x) \equiv 0 \pmod {x^n}$

先前我们假定了 $F(x)*G(x) \equiv 1 \pmod {x^n}$ ，所以可以代入化简得

$G(x)+F(x)H^2(x)-2H(x) \equiv 0 \pmod {x^n}$

即

$G(x) \equiv 2H(x)-F(x)H^2(x) \pmod {x^n}$

$G(x) \equiv H(x)[2-F(x)*H(x)]\pmod {x^n}$

多项式求逆只需要按照上式递推即可。

但这里有个问题。先前我们在思考 $H(x)$ 的时候是在模 $x^{n/2}$ 意义下的，而在这个式子里，当我们用到 $H(x)$ 的时候是在模 $x^n$ 意义下的，那么 $H(x)$ 的高次项会有影响吗？事实上，我们已经通过证明保证了 $P^2(x)$ 的前 $n-1$ 项都为0，而这之后的变换又都是等价变换，因此我们知道最终得到的结果是正确的，并且一定是与 $H(x)$ 的高次项无关的。只需要保证前后的两个 $H(x)$ 的高次项是相同的即可。