多项式exp/牛顿迭代-526互联

牛顿迭代解决的是这样一个问题：已知 \(g(f(x))\equiv 0\pmod {x^n}\) 与 \(g(x)\)，求模 \(x^n\) 意义下的 \(f(x)\)
这个问题可以用倍增的方式解决。首先假设你知道了 \(g(f(x))=0\) 的常数项（一般都能很方便的知道）。
然后，我们假设 \(f_0(x)\) 是模 \(x^{\lceil\frac{n}{2}\rceil}\) 意义下的答案，这个是已经求出来了的答案。
将 \(f(x)\) 在 \(f_0(x)\) 的位置上进行泰勒展开（附赠通用展开公式），得到 \(\sum_{i=0}^{\infty} \frac{g^{(i)}(f_0(x))}{i!}(f(x)-f_0(x))^i\equiv 0\pmod {x^n}\)，其中 \(f^{(i)}\) 指的是对函数 \(f(x)\) 进行 \(i\) 次求导。
考虑到 \(f(x)-f_0(x)\) 在 \(\lceil\frac{n}{2}\rceil\) 之前的位置上（不包含）一定是没有值的（因为是取模意义下的，所以 \(f(x)\) 和 \(f_0(x)\) 在这些项上的值一定相同），所以对于所有 \(2\le i\)，\((f(x)-f_0(x))^i\equiv 0\pmod{x^n}\)，然后上面那一大坨求和式就只会保留前两项，也就是 \(g(f_0(x))-g'(f_0(x))(f(x)-f_0(x))\equiv 0\pmod{x^n}\)，然后把这个东西解掉就可以得到 \(f(x)=f_0(x)-\frac{g(f_0(x))}{g'(f_0(x))}\pmod{x^n}\)，然后这个东西就可以在倍增里直接做了！