January 4, 2023

Relaxed Convolution(Online FFT)によるexp/inv/log/sqrt/pow 【備忘録】

初めに

この記事ではあくまでも時間計算量のオーダーのみを考慮しているため、定数倍についての保証はありません。

relaxed convolution とは

$\mathcal{O}(N\log ^2 N)$ で多項式の積を計算するオンラインアルゴリズムです。Online FFT と呼ばれる事もありますが、Relaxed Convolution の方が使われていそうだったのでこちらで統一します。
このアルゴリズムを使うことで形式的べき級数の $\exp$ / $\mathrm{inv}$ / $\log$ 等も出来ます。

relaxed convolution のやり方

Kiri さんのわかりやすい解説があったのでここでは割愛させて下さい

積分のやり方

$\int f dx$ の $N$ 項目は、 $f$ の $N-1$ 項目に $N$ をかけた物なので、一つ前の項を保存しておけば出来ます。

exp(f) のやり方

g=\exp(f)

とおくと、

\int gf' dx =\exp(f)=g

より、 $g$ の $N-1$ 項目までと、 $f'$ の $N-1$ 項目までを relaxed convolution にて掛け合わせる事で出来ます。

verify : https://judge.yosupo.jp/submission/119568

relaxed convolution を高々定数項だけずらす拡張

$f$ の $N-t$ 項目まで、 $g$ の $N-t$ 項目までをかけ合わせたものの $N$ 項目までを手に入れることが出来ます。
$f=f_0+f_1x^t$ ( $\mathrm{deg}(f_0) \lt t$ )、 $g=g_0+g_1x^t$ ( $\mathrm{deg}(g_0) \lt t$ ) とおくと、

fg=f_0g_0+(f_1g_0+f_0g_1)x^t+f_1g_1x^{2t}

$f_0$ と $g_0$ に関しては高々定数項しかないため前半 3 項は愚直に計算しても計算量はボトルネックとなり得ません。
また、 $N \geq t$ の場合、 $f$ の $N-t$ 項目は $f_1$ の $N-2t$ 項目であることから、 $f_1$ と $g_1$ を relaxed convolution で掛け合わせる事で $f_1g_1$ の $N-2t$ 項目まで手に入り、
これにより $fg$ の $N$ 項目までを手に入れる事が出来ました。
これは Kiri さんのブログの図の左上の $1 \times 1$ のマスを増やしたと考えると直感的に理解出来るかと思います。
また、f と g の項数が高々定数個ずれる場合、小さい方に合わせてあげれば良いです。

inv のやり方

$g=1/f$ とおくと、 $fg-1=0$ であることから、

[x^N] fg = [x^N] (f \bmod x^{N-1}) \times (g \mod x^{N-1}) + ([x^0]f \times [x^N]g + [x^N]f \times [x^0]g)

を前章の拡張を用いて計算する事で $g$ の $N$ 項目を求める事が出来ます。

verify : [https://judge.yosupo.jp/submission/119569$

log のやり方

$g=\log f$ とおくと、 $g=\int \frac{f'}{f} dx$ であることから前章までの内容を用いて計算することが出来ます。
(23/01/08/9:53 追記) $h=\frac{f}{g}$ とおくと $gh=f$ となり、これは inv とほぼ同様に処理出来るので一回の relaxed convolution で行う事も出来ます。

verify : https://judge.yosupo.jp/submission/119575

sqrt のやり方

$f$ の初項を非零に限定すると、 $g=\sqrt f$ とおくと、 $g^2=f$ であることから inv の章と同様に一つだけ項数をずらすことで出来ます。
初項が零の時はそもそも $N$ 項目までの情報から $2N$ 項目までに非零が存在するかを知り得ないので定義から難しそうです。
(そもそも形式的冪級数の sqrt は定数項 1 を前提とするのが一般的という話もあります)

verify : TODO

pow のやり方

$f^M=\exp (M\log (f))$ を使えば出来ます。
例の如く $\log$ の適用条件等に注意する必要があります。