多项式全家桶（二）：多项式的逆，导，积

         ,       这一部分麻烦一点了，但是很重要，几乎所有多项式都得用的，不过好在也不是很复杂的。

1. 多项式求逆

         ,       P4238 【模板】多项式求逆

         ,       求一个多项式 A A A 的模 x n x^n xn 的逆元 B B B 时，假设先求出了模 x n 2 x^{frac{n}{2}} x2n/span> 的逆元 B ′ B' B′，既：

A B ′ ≡ 1   ( m o d   x n 2 ) A*B' equiv 1 (mod x^{frac{n}{2}}) A/span>B′≡1 (mod x2n/span>)

A B ≡ 1   ( m o d   x n ) A*B equiv 1 (mod x^{n}) A/span>B≡1 (mod xn)

         ,       那么显然存在：

A B ≡ 1   ( m o d   x n 2 ) = A B ′ A*B equiv 1 (mod x^{frac{n}{2}})=A*B' A/span>B≡1 (mod x2n/span>)=A/span>B′

B B ′ ≡ 0   ( m o d   x n 2 ) B-B' equiv 0 (mod x^{frac{n}{2}}) B/span>B′≡0 (mod x2n/span>)

         ,       两边同时平方：

B 2 2 B B ′ + B ′ 2 ≡ 0   ( m o d   x n ) B^2-2BB'+B'^2 equiv 0 (mod x^n) B2/span>2BB′+B′2≡0 (mod xn)

         ,       再把 A A A 乘回去：