この解説はユーザー解説です

解説の末尾に「多項式のニュートン法でも解ける」と書きましたが、容易ではないので簡単に付記します。

多項式のニュートン法とは次のようなものです。

\(A(F) = 0\) を満たす \(F\) を求めたい。(\([x^0]F\) はもともとわかっているとする。) \(\hat{F}(x) = F(x) \bmod {x^d}\) がわかっているときに

\[A(F) = A(\hat{F}) + A'(\hat{F})(F - \hat{F}) + \mathrm{O}((F - \hat{F})^2)\]

の両辺を \(\bmod{x^{2d}}\) を取ると \(\mathrm{O}((F - \hat{F})^2)\) が無視できるので

\[A(F) \equiv A(\hat{F}) + A'(\hat{F})(F - \hat{F}) \pmod{x^{2d}}\]

から \(F \mod x^{2d}\) を計算できる。

今、

\[A(F) = x\exp\left(\sum_{0 \lt k} \frac{F(x^k) + G(x^k)}{k}\right) - F(x) - x = 0, F(0) = 0\]

を満たす \(F\) を求めましょう。式変形すると

\[ \begin{aligned} &A(F) \\ &= x\exp\left(\sum_{0 \lt k} \frac{G(x^k)}{k}\right) \exp\left(\sum_{0 \lt k} \frac{F(x^k)}{k}\right) - F(x) - x \\ &= x \exp\left(\sum_{0 \lt k} \frac{G(x^k)}{k}\right) \exp\left(\sum_{2 \leq k} \frac{F(x^k)}{k}\right) \exp F(x) - F(x) - x \\ \end{aligned} \]

となります。
ここで \(x \exp\left(\sum_{0 \lt k} \frac{G(x^k)}{k}\right)\) は \(F\) の値に依存しない定数です。
また、\(\exp\left(\sum_{2 \leq k} \frac{F(x^k)}{k}\right)\) は、式をよく見ると \(F \bmod {x^d}\) がわかっていれば \(\bmod {x^{2d}}\) 上で正確に計算にできる、すなわち言い換えるとニュートン法の手順内において

\[\exp\left(\sum_{2 \leq k} \frac{\hat{F}(x^k)}{k}\right) \equiv \exp\left(\sum_{2 \leq k} \frac{F(x^k)}{k}\right)\pmod{x^{2d}} \]

が成り立っていることがわかるので、ニュートン法の手順においては定数とみなしても \(\bmod {x^{2d}}\) 上で正確に計算するうえでは問題ないとわかります。(ここちょっとズルいと思うんですが許してください><)

よって

\[ P(x) = x \exp\left(\sum_{0 \lt k} \frac{G(x^k)}{k}\right) \exp\left(\sum_{2 \leq k} \frac{F(x^k)}{k}\right) \]

とおいて

\[ A(F) = P(x) \exp F(x) - F(x) - x\]

\[ A'(F) = P(x) \exp F(x) - 1\]

を元にニュートン法を繰り返していけばよいです。 (\(\exp F(x)\) 自体もニュートン法により求められます。)