はじめに
Power Projection とは以下の問題のことを指します。
- FPS(形式的冪級数) $f(x), g(x)$ が与えられるので、$i = 0, 1, \dots, n$ について、$[x^{n}]f(x)^{i}g(x)$ を求めてください。
この問題は noshi91 さんによって、$\Theta(n\log(n)^{2})$ で解けることが発見されました。
noshi91 さんによる初出のブログ : FPS の合成と逆関数、冪乗の係数列挙 $\Theta(n\log(n)^{2})$
maspy さんによる実装方針を含めた解説ブログ : FPS 合成・逆関数の解説（１）逆関数と Power Projection
本題
- FPS $f(x), g(x)$ が与えられるので、$i = 0, 1, \dots, n$ について、$[x^{i}]f(x)^{i}g(x)$ を求めてください。
求める係数が $x^{n}$ から $x^{i}$ に変わっています。
解説
$[x^{0}]f(x) = 0$ のときは、$[x^{i}]f(x)^{i}g(x) = ([x^{1}]f(x))^{i}[x^{0}]g(x)$ が成り立つので簡単に求められます。以降、$[x^{0}]f(x) \neq 0$ であるとします。
まず、以下の等式が成り立ちます。
$[x^{i}]f(x)^{i}g(x) = [x^{n}]x^{n - i}f(x)^{i}g(x)$
ここで、$k = n - i$ とします。すると、以下のように変形できます。
$[x^{n}]x^{n - i}f(x)^{i}g(x) = [x^{n}]x^{k}f(x)^{n - k}g(x) = [x^{n}] (xf(x)^{-1})^{k}(f(x)^{n}g(x))$
よって、$k = 0, \dots, n$ に対して、上記の値を求めることができれば元の問題を解くことができます。
$f(x)^{-1}$ と $f(x)^{n}$ の $n$ 次までの値が分かればこの問題は Power Projection と全く同じ形になっているので解くことができるのですが、これらは高速に解けることが知られています。
maspy さんのブログ : 多項式・形式的べき級数-高速に計算できるもの
実装例
AtCoder Library と自分が使っているライブラリを用いて、例えば以下のように書くことができます。
#include "po167_library/fps/FPS_Power_Projection.hpp" #include "po167_library/fps/FPS_pow.hpp" // n := |f(x)| = |g(x)| // return i = 0, 1, ... n - 1 // [x^{i}] g(x) f(x)^{i} // = [x^{n - 1}] f^{n - 1}g (xf^{-1})^{n - 1 - i} template<class T> std::vector<T> power_projection_2(std::vector<T> g, std::vector<T> f){ int n = g.size(); assert((int)f.size() == n); if (n == 0) return {}; std::vector<T> res(n); if (f[0] == 0){ res[0] = g[0]; for (int i = 1; i < n; i++){ res[i] = res[i - 1] * f[1]; } return res; } std::vector<T> G = atcoder::convolution(g, po167::FPS_pow(f, n - 1)); G.resize(n); f = po167::FPS_inv(f); f.pop_back(); f.insert(f.begin(), 0); res = po167::Power_Projection(G, f, n); std::reverse(res.begin(), res.end()); return res; }
出題例
The 4th Universal Cup. Stage 17 F
数列 $A$ が与えられます。$n = 1, 2, \dots, N$ について、以下の条件を全て満たす 01 文字列の場合の数を $998244353$ で割ったあまりを求めてください。
- 長さが $2n$
- 文字列に含まれる 0, 1 の数が等しい
- 末尾に連続する 0 の数を $a$ としたとき、$a$ は数列 $A$ に含まれる
解説
この問題自体は log 1 つで解けるらしいですが、自分はまだ理解できていないので今回は省略します。
1 を境目としてみることで、以下の問題に帰着できます。
- 長さ $n + 1$ の非負数列 $B$ であって、総和が $n$ かつ $B_{n + 1}$ が $A$ に含まれるものは何通りですか。
$f(x) = 1 + x + \cdots = \dfrac{1}{1 - x}$ と置くことで答えは以下のようになります。
$\displaystyle\sum_{a\in A}[x^{n - a}] f(x)^{n}$
$g(x) = \displaystyle\sum_{a\in A} x^{a}$ とすると、答えは $[x^{n}] f(x)^{n} g(x)$ と表せ、Power Projection の亜種に帰着できました。この問題では $f(x)$ の pow や inv は線形で求められますが、計算量には影響しないです。
#include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; int main() { int N, M; std::cin >> N >> M; std::vector<mint> A(N + 1); for (int i = 0; i < M; i++){ int a; std::cin >> a; A[a] = 1; } std::vector<mint> B(N + 1, 1); auto ans = power_projection_2(A, B); for (int i = 1; i <= N; i++){ std::cout << ans[i].val() << "\n"; } }
終わり
既に知られた話かも知れませんが、自分は知らなかった/頭に残っていなかったので記事にしました。
これはただの意思表明なのですが、これからは積極的にアウトプットしていきたいと思います。
