多项式学习笔记

目录

• 多项式学习笔记
  • 多项式乘法逆

多项式乘法逆

给出 \(F(x)\)，求 \(G(x)\) 使得 \(F(x)G(x) \equiv 1 (\bmod x^n)\)。

首先 \(G_0(x)=\frac{1}{F_0(x)}\)，然后考虑倍增，用 \(\bmod x^{ \left \lceil \frac{n}{2} \right \rceil }\) 的答案推 \(\bmod x^n\) 的答案：

\[\begin{aligned} & \because F(x)G'(x) \equiv 1 (\bmod x^{ \left \lceil \frac{n}{2} \right \rceil }) \\ & \because F(x)G(x) \equiv 1 (\bmod x^{ \left \lceil \frac{n}{2} \right \rceil }) \\ & \therefore G(x)-G'(x) \equiv 0 (\bmod x^{ \left \lceil \frac{n}{2} \right \rceil }) \\ & \therefore (G(x)-G'(x))^2 \equiv 0 (\bmod x^{n}) \\ & \therefore G(x)^2-2G(x)G'(x)+G’^2(x) \equiv 0 (\bmod x^{n}) \\ & \therefore G(x)-2G'(x)+F(x)G’^2(x) \equiv 0 (\bmod x^{n}) \\ & \therefore G(x) \equiv 2G'(x) – F(x)G’^2(x) (\bmod x^{n}) \\ \end{aligned} \]

需要用到 \(O(n \log n)\) 的多项式乘法，计算一下复杂度：

\[T(n)=T(\left \lceil \frac{n}{2} \right \rceil )+O(n \log n) \]

所以复杂度 \(T(n)=O(n \log n)\)。