浅谈多项式求逆与多项式除法

多项式求逆

对于一个n-1(不妨令n为2的幂次)次多项式A(x),我们要求出一个多项式B(x)使得:
$A(x)B(x)\equiv 1(\mod x^n)$
我们可以使用递归的方法进行求解:
假定我们已经求出一个多项式G(x)使得:
$A(x)G(x)\equiv 1(\mod x^{\frac{n}{2}})$
我们可以证明对于任意$P(x)\equiv 0(\mod x^{\frac{n}{2}})$,有$P^2(x)\equiv 0(\mod x^n)$
所以:
$(A(x)G(x)-1)^2\equiv 0(\mod x^n)$
$A(x)G(x)(2-A(x)G(x))\equiv 1(\mod x^n)$
求$G(x)(2-A(x)G(x))$即可。
时间复杂度是形如$T(n)=T(n/2)+O(n\lg n)$的式子,所以是$O(n\lg n)$的。
模板细节略微有点多

多项式除法

多项式除法我们要解决的是这样一个问题:
给定两个多项式$A(x)$,$B(x)$,要求两个多项式$C(x)$和$D(x)$使得,$D(x)$的次数小于$B(x)$的次数并且$A(x)=B(x)C(x)+D(x)$。
如果我们确信$D(x)$为0,那么直接多项式求逆即可。但是如果$D(x)$不是0,那么这个问题就有点麻烦了。
不妨设$A(x)$为一个n次多项式,$B(x)$为一个m次多项式,则$C(x)$是一个n-m次多项式。
令:
$A_R(x)=x^nA(\frac{1}{x})$
$B_R(x)=x^mB(\frac{1}{x})$
$C_R(x)=x^{n-m}C(\frac{1}{x})$
由于:$A(\frac{1}{x})=B(\frac{1}{x})C(\frac{1}{x})+D(\frac{1}{x})$
所以:$A_R(x)=B_R(x)C_R(x)+D_R(x)x^{n-m+1}$
$A_R(x)\equiv B_R(x)C_R(x)(\mod x^{n-m+1})$
由于$C_R(x)$最高次项只有n-m,所以我们只需要求出$B_R(x)$在n-m+1次项下的逆就可以计算出$C_R(x)$然后算出$C(x)$,然后直接计算$D(x)$即可。
代码细节有点多,主要是要注意$x^{n-m+1}$的模数以及不要把一些后面还要用的东西直接NTT掉。

例题

[洛谷P4841][国家集训队]城市规划
[loj#2409][THUPC2017]sum

Tagged with:

发表评论