多项式求逆
考虑倍增。
若已经求出 \(A \times B' \equiv 1 \pmod {x^n}\)，我们希望求出 \(B\) 使得 \(A \times B \equiv 1 \pmod {x^{2n}}\)。
有：
\[B - B' \equiv 0 \pmod {x^n} \]\[(B - B')^2 \equiv 0 \pmod {x^{2n}} \]\[B^2 - 2 B B' + B'^2 \equiv 0 \pmod {x^{2n}} \]两边同乘 \(A\)，有：
\[B - 2B' + AB'^2 \equiv 0 \pmod {x^{2n}} \]所以：
\[B \equiv 2B' - AB'^2 \pmod {x^{2n}} \]注意应该倍增到最小的 \(2^t\) 使得 \(2^t \ge n\)。
时间复杂度 \(O((n + \frac{n}{2} + \frac{n}{4} + \cdots) \log n) = O(n \log n)\)。
标签：AB,log,pmod,多项式,全家,2n,equiv From： https://www.cnblogs.com/zltzlt-blog/p/18146944