多项式求逆和除法

对于一个多项式$A(x)$,如果存在另一个多项式$B(x)$,有$deg B(x) deg A(x) $,且$A(x)B(x) (x^{{n})$,那么称$B(x)$为$A(x)$在$x}{n}$下的逆元,记为$A^{-1}(x)$

当$n=1$时,$A(x) \equiv c (\mod x)$,此时$A^{-1}(x) \equiv c^{-1}$

不妨设$A(x)B^{'}(x) \equiv 1 (\mod x^{\lceil \frac{n}{2} \rceil})$,$A(x)B(x) \equiv 1 (\mod x^{n})$

显然,也有$A(x)B(x) \equiv 1 (\mod x^{\lceil \frac{n}{2} \rceil})$

和第一个式子相减,可得$B(x) \equiv B^{'}(x) (\mod x^{\lceil \frac{n}{2} \rceil})$

移项,两边平方,有$B^{2}(x)-2B(x)B^{'}(x)+B^{'2}(x) \equiv 0 (\mod x^{n})$

两边同乘$A(x)$,化简可得$B(x) \equiv 2B^{'}(x)-A(x)B^{'2}(x) (\mod x^{n})$

于是就可以根据最后一个式子递归计算了.在计算的时候需要拿NTT来实现多项式乘法的过程.总的时间复杂度为$O(n\log n)$.

在写了在写了

周末填坑