noshi91のメモ

データ構造のある風景

FPS の合成と逆関数、冪乗の係数列挙 Θ(n (log(n))^2)

概要

温めておいたのですが、ABC で似た問題が出題されてしまったので (想定解は違いましたが) 起源が問題になる前に公開しようと思います。

問題

標数の十分大きい体 \mathbb{K} 上の形式的冪級数 f ( x ) \in \mathbb{K} \lbrack \lbrack x \rbrack \rbrack の k 次までの項が与えられる。 \lbrack x ^ k \rbrack f ( x ) ^ 0 , \lbrack x ^ k \rbrack f ( x ) ^ 1 , \dots , \lbrack x ^ k \rbrack f ( x ) ^ {n - 1} を求めよ。 ただし、 \mathbb{K} を係数とする次数 n の多項式乗算が \mathrm{O} ( M ( n ) ) で可能とする。

本記事では、この問題に対する時間計算量 \mathrm{O} ( M ( n + k ) \log ( n + k ) ) のアルゴリズムを提案する。

アルゴリズム

まず、 \lbrack x ^ 0 \rbrack f ( x ) = 0 の場合に帰着できる。 何故なら、 c := \lbrack x ^ 0 \rbrack f ( x ) とすれば \lbrack x ^ k \rbrack f ( x ) ^ i = \sum _ {j = 0} ^ {i} \binom{i}{j} c ^ j \lbrack x ^ k \rbrack ( f ( x ) - c ) ^ { i - j } であり、 f ( x ) - c に対する答えから畳み込みで求まるためである。

2 変数形式的冪級数 \mathbb{K} \lbrack \lbrack y \rbrack \rbrack \lbrack \lbrack x \rbrack \rbrack 上で *1 、以下の値が y についての多項式として n - 1 次まで求められればいい。

\begin{align} [x ^ k] \sum _ {i = 0} ^ {\infty} y ^ i f ( x ) ^ i = [x ^ k] \frac{1}{1 - y f ( x )} \end{align}

\lbrack x ^ 0 \rbrack f ( x ) = 0 と仮定したため分母の x ^ 0 の係数は 1 であり、分母が可逆であるからこの式変形は正当である。

これに Bostan-Mori 法 [1] を適用すると、分子と分母の y についての次数がループごとに倍々になってしまう。 しかし x ^ k の係数を求めるためには分子と分母は x について k 次までしか必要ないため、 x についての次数は半々になっていく。 結局、 t 回目のイテレーションにおいては x について k / 2 ^ t 次、 y について 2 ^ t 次の 2 変数多項式の乗算を行うことになり、時間計算量は \mathrm{O} (M (k) ) となる。 よって全体で時間計算量は n + \mathrm{O} (M ( k ) \log (k) ) であり、 \lbrack x ^ 0 \rbrack f ( x ) の場合に畳み込みが必要なことと併せても \mathrm{O} ( M ( n + k ) \log ( n + k ) ) で抑えられる。

応用

[Tutorial] Generating Functions in Competitive Programming (Part 2) - Codeforces この記事の Lagrange Inversion Formula の項で、 f の逆関数 g に対して \left ( g ( x ) / x \right ) ^ k の計算ができれば冪乗の係数の列挙ができることが示されている。 逆に前述のアルゴリズムにより冪乗の係数を列挙すれば、 \left ( g ( x ) / x \right ) ^ k が分かるため g を \Theta ( n ( \log ( n ) ) ^ 2 ) で求めることができる。

さらに、逆関数の計算と同じ時間計算量で合成の計算ができることが分かっているため [2]、合成も \Theta ( n ( \log ( n ) ) ^ 2 ) となる。

参考文献

[1] Bostan, A., & Mori, R. (2021). A simple and fast algorithm for computing the N-th term of a linearly recurrent sequence. In Symposium on Simplicity in Algorithms (SOSA) (pp. 118-132). Society for Industrial and Applied Mathematics.

[2] Brent, R. P., & Kung, H. T. (1978). Fast algorithms for manipulating formal power series. Journal of the ACM (JACM), 25(4), 581-595.

*1: 少し注意すると、 \mathbb{K} \lbrack y \rbrack \lbrack \lbrack x \rbrack \rbrack で議論しても良い。