前書き

形式的冪級数のいろいろな変形を調べていると,

ニュートン法を利用して $O(n\log n)$ で求めることができます

という説明のもとわけわからん式が書いてあることがしばしばあります

なんでこんな式が出てくるのかをちゃんと考えようの会です

本文

ニュートン法を使うのですが, いきなりfpsは難しいのでまず実数で考えてみます

関数 $F(x)$ があって, $F(x) = a$ の解を探したいとする

いい感じの初期値 $x_0$ を決める

$F(x)$ を $x = x_0$ の周りでテイラー展開すると

F(x) = F(x_0) + F'(x_0)(x - x_0) + O((x - x_0)^2)

と書ける

いい感じに移項したら

\begin{aligned}
x_{n + 1} = x_n - \dfrac{F(x_n) - a}{F'(x_n)} \cr
\end{aligned}

というニュートン法の式になり, 繰り返し計算していくことで２次の速さで収束していく

これと同じことを形式的冪級数でやりたい

$F(g) = f \pmod {x^n}$ となるような $g$ が求めたい

先ほどの式に代入すると

\begin{aligned}
g_{n + 1} = g_n - \dfrac{F(g_n) - f}{F'(g_n)} \cr
\end{aligned}

ここで, $g \equiv g_n \pmod {x^{2^n}}$ をみたすとすると, $(g - g_n)^2 \equiv 0 \pmod {x^{2^{n+1}}}$ をみたす

したがって, $g \equiv g_n \pmod {x^{2^n}}$ のとき $g \equiv g_{n+1} \pmod {x^{2^{n+1}}}$

という感じに $[x^0]g$ を求めることができればそこから精度を倍にしていける

さて, この $F$ とは具体的にどのようなものでしょうか

逆元を求めたい場合

つまり

$g^{-1} = f \pmod {x^n}$ となるような $g$ が求めたい

とすると

\begin{aligned}
g_{n + 1} &= g_n - \dfrac{F(g_n) - f}{F'(g_n)} \cr
&= g_n - \dfrac{g_n^{-1} - f}{-g_n^{-2}} \cr
&= 2g_n - f g_n^2 \cr
\end{aligned}

という感じで導出できました

$\exp$ も同じ方法でできて,

$g = \exp f$ が求めたい, つまり

$\log g = f \pmod {x^n}$ となるような $g$ が求めたい

とすると

\begin{aligned}
g_{n + 1} &= g_n - \dfrac{F(g_n) - f}{F'(g_n)} \cr
&= g_n - \dfrac{\log g_n - f}{g_n^{-1}} \cr
&= g_n(1 - \log g_n + f) \cr
\end{aligned}

と導出できる

肝心の計算量だが, 毎回定数回の畳み込みをして長さが倍になっていくので

\begin{aligned}
T(N) &= O(N\log N) + O(\dfrac{N}{2}\log \dfrac{N}{2}) + \ldots \cr
&= O(N\log N)
\end{aligned}

となる

おわりに

こういうのをちゃんと導出法から知ってると, ソラで書かないといけなくなったときとかに便利

参考文献

【競技プログラミング】形式的冪級数の応用テクニック(前編)