我们记\(deg(A)\)为多项式\(A(x)\)的度，即为\(A(x)\)的最高项系数 + 1

对于多项式\(A(x)\)，如果存在\(B(x)\)满足\(deg(B) \le deg(A)\)，且

\[A(x)B(x) \equiv 1 \pmod {x^{n}}\]

我们称\(B(x)\)为\(A(x)\)在模\(x^n\)意义下的逆元，记作\(A^{-1}(x)\)

求解过程

考虑递归求解

当\(n = 1\)时，\(A(x) \equiv c \pmod x\)，显然\(A^{-1}(x)\)就是\(c^{-1}\)

倘若我们要计算

\[A(x)B(x) \equiv 1 \pmod {x^n}\]

而已经计算出

\[A(x)B'(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}}\]

我们要求的\(B(x)\)当然也满足

\[A(x)B(x) \equiv 1 \pmod {x^{\lceil \frac{n}{2} \rceil}}\]

两式相减

\[A(x)(B(x) - B'(x)) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}\]

即

\[B(x) - B'(x) \equiv 0 \pmod {x^{\lceil \frac{n}{2} \rceil}}\]

两边平方，由于对于平方后的多项式\(C(x)\)，其系数\(c_i = \sum\limits_{j = 0}^{i} b_j*b'_{i - j}\)，必有一项小于\(\lceil \frac{n}{2} \rceil\)而使\(c_i = 0\)

所以平方后放到\(\mod x^{n}\)意义下依然成立

\[B^2(x) + B'^2(x) - 2B(x)B'(x) \equiv 0 \pmod {x^{n}}\]

两边乘\(A(x)\)

\[B(x) + A(x)B'^2(x) - 2B'(x) \equiv 0 \pmod {x^{n}}\]

得到

\[B(x) \equiv B'(x)(2 - A(x)B'(x)) \pmod {x^{n}}\]

可以使用\(fft\)优化成\(O(nlogn)\)

总时间复杂度\(T(n) = T(\lceil \frac{n}{2} \rceil) + O(nlogn) = O(nlogn)\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include