歴史

このコンテスト終了直後に、noshi91 さんによる以下の記事が公開されました。

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

この記事では、Power Projection という問題に対して、より良い計算量のアルゴリズムを発見したことと、そのことによって、FPS の合成と逆関数の計算量も改善されたことが記されています。

Power Projection とは簡単にいうと以下の問題のことです。

高々 \((N - 1)\) 次の多項式 \(f(x), g(x)\) と整数 \(M\) が与えられます。\(i = 0, 1, \dots , M - 1\) に対して \([x^{N - 1}]g(x)f(x)^{i}\) を求めてください。

この問題を \(O((N + M) \log(N + M)^{2})\) で解けることが上の記事に記されています。

実装方針を含む詳しい解説は maspy さんによる以下の記事にまとまっています。

FPS 合成・逆関数の解説（１）逆関数と Power Projection

このアルゴリズムを記した論文は、理論計算機科学のトップ国際会議の一つである FOCS2024 に採択されたそうです。

noshi91 さんによる報告

解法

公式解説 を見ればわかることですが、\(i\) 回の操作でマス \(N\) に辿り着けない確率を \(a_{i}\) とおくと、以下の関係式が成り立ちます。

\[P_{i} = a_{i - 1} - a_{i}\]

よって、\(i = 0,1, \dots , N\) に対する \(a_{i}\) を求めることができれば答えが求まります。

まず、多項式 \(f(x), g(x)\) を以下のように定義します。

\[f(x) = \dfrac{1}{K}(x + x ^ {2} + \cdots + x^{K})\]

\[g(x) = (1 + x + \cdots + x^{N -1})\]

これらの式と \(a_{i}\) について、以下の式が成り立ちます。

\[a_{i} = \sum_{k = 0}^{N - 1}[x^{k}]f(x)^{i}\]

\[a_{i} = [x^{N - 1}] g(x)f(x)^{i}\]

上記した Power Projection の問題が十分高速に解けることから、 \(a_{i}\) も求まります。よって、 \(P_{i}\) も高速に求めることができます。計算量は \(O(N\log(N)^{2})\) です。

c++ による実装例