求 \(f \ast g \bmod {x^n}\) ，要开二倍数组，取前 \(n\) 项。
要求 \(g(f(x)) \equiv 0 \pmod {x^n}\)，考虑倍增。
\(n=1\) 时不难得到 \(f\) 的值。
设当前答案为 \(f_0 \pmod {x^{n/2}}\)，想求出 \(f \pmod {x^n}\)。通过式子 \(f \equiv f_0 - \cfrac{g(f_0)}{\cfrac{dg(f_0)}{df}}\)（证明见 OI Wiki）可知。
多项式牛顿迭代 学习笔记
发布时间 2023-07-26 10:35:15作者: 383494