この問題は 前回 に引き続き母関数をテーマとして作られた問題です。
前回はかなりテクニックに寄った話を中心に書いたので、今回はテクニックよりもイメージに寄った話を書いていきましょう。

母関数のイメージ

母関数とは数列 \(a_n\) を係数に持つ関数、ということを前回書きました。しかしこの説明では、「数え上げる “モノ”」と「母関数」の関係がどうにもはっきりしません。
そこで、ここでは数え上げる “モノ” およびその “集まり” と母関数がどのように密接に関わっているのかをを別の視点から捉えて説明します。

数え上げの問題では、必ず数え上げる “モノ” (グラフ, 文字列, 操作列, …) 、およびそれらからなる “集まり” (集合) が存在します。この集合が良い性質を持っているとき、集合を母関数に置き換えて考えることができます。

わかりやすさのため、以下の説明では数列・母関数・集合を次に挙げる文字種を使用した表記で統一します。

• 数列 \(\to\) 小文字 斜体 (\(a, b, c, \dots\))
• 母関数 \(\to\) 大文字斜体 (\(A, B, C, \dots\))
• 集合 \(\to\) 大文字筆記体 (\(\mathcal{A}, \mathcal{B}, \mathcal{C}, \dots\) )

例としてまずは次の簡単な問題を考えてみましょう。

高橋君は弁当を買うことにしました。
食堂 A では \(i\) 円の弁当が \(a_i\) 個売られています。\((1 \leq i \leq 1000)\)
食堂 B では \(j\) 円の弁当が \(b_j\) 個売られています。\((1 \leq j \leq 1000)\)

(1) 高橋君は A か B の いずれか で弁当を \(1\) 個買うことにしました。どのような組合せが考えられますか？
(2) 高橋君は A と B の 両方 で弁当を \(1\) 個ずつ買うことにしました。どのような組合せが考えられますか？
(3) 「\(n\) 円かかる弁当の買い方の通り数 \(a_n\) 」の母関数を考えます。(1), (2) を母関数で表してください。

たとえば A で \(1\) 円と \(2\) 円の弁当が \(1\) 個ずつ、B で \(1\) 円と \(3\) 円の弁当が \(1\) 個ずつ場合を例として定式化してみましょう。
食堂 A の弁当を \(1\)、食堂 B の弁当を \(1^\ast\) のように表します。すると、食堂 A, B の弁当からなる集合 \(\mathcal{A}, \mathcal{B}\) は

\[ \mathcal{A} = \lbrace 1, 2 \rbrace , \mathcal{B} = \lbrace 1^\ast , 3^\ast \rbrace \]

となります。
(1), (2) で数え上げる対象も同様に集合で表していきましょう。
(1) で問われている操作は交わりを持たない集合同士をマージする操作で、(2) で問われているのは集合から \(1\) 個ずつ取り出して組み合わせる操作です。
これらの操作は集合に対する広義の直和(非交和)・直積とみなすことができるので、(1) の操作を \(+\), (2) の操作を \(\times\) で表すことにしましょう。
たとえば上の例だと \(\mathcal{A} + \mathcal{B}, \mathcal{A} \times \mathcal{B}\) は次のようになります。

\[ \begin{aligned} \mathcal{A} + \mathcal{B} &= \lbrace 1,2,1^\ast, 3^\ast \rbrace \\ \mathcal{A} \times \mathcal{B} &= \lbrace 1, 2 \rbrace \times \lbrace 1^\ast , 3^\ast \rbrace \\ &= \lbrace (1,1^\ast), (1,3^\ast), (2,1^\ast), (2,3^\ast) \rbrace \end{aligned} \]

さて、次はこの集合を母関数に置き換えてみましょう。

\(\mathcal{A}, \mathcal{B}\) の母関数 \(A(x), B(x)\) は

\[ A(x) = \sum_i a_i x^i, B(x) = \sum_j b_j x^j\]

となります。 (1), (2) に対応する母関数は、実は \(A(x)\) と \(B(x)\) を用いて記述することができます。
まずは \(\mathcal{A} + \mathcal{B}\) です。集合 \(\mathcal{A}, \mathcal{B}\) が背反ならば、

• (\(\mathcal{A}\) に含まれる \(n\) 円の買い方) + (\(\mathcal{B}\) に含まれる買い方) = (\(\mathcal{A} + \mathcal{B}\) に含まれる\(n\) 円の買い方)

が成り立つので、 (1) で \(i\) 円使う買い方を \(c_i\) としたとき

\[ c_i = a_i + b_i\]

が成り立ちます。上の式から (1) の母関数 \(C(x)\) は

\[ \begin{aligned} C(x) &= \sum_{i} (a_i + b_i) x^i \\ &= A(x) + B(x) \end{aligned} \]

であることがわかります。

次に \(\mathcal{A} \times \mathcal{B}\) です。(2) で \(i\) 円使う買い方を \(d_i\) としたとき、

\[ d_k = \sum_{i + j = k} a_i b_j\]

となるので、

\[ \begin{aligned} D(x) &= \sum_k \left(\sum_{i+j = k} a_i b_j\right) x^k \\ &= \sum_i a_i x^i \sum_j b_j x^j \\ &= A(x) \times B(x) \end{aligned} \]

となることが分かります。結局まとめると

\[\mathcal{C} = \mathcal{A} + \mathcal{B} \iff C(x) = A(x) + B(x)\]

\[\mathcal{D} = \mathcal{A} \times \mathcal{B} \iff D(x) = A(x) \times B(x)\]

となることがわかります。たとえば \(\mathcal{A} = \lbrace 1, 2 \rbrace ,\mathcal{B} = \lbrace 1^\ast , 3^\ast \rbrace\) の場合、

\[ A(x) = x + x^2, B(x) = x + x^3\]

\[C(x) = A(x) + B(x) = 2x + x^2 + x^3\]

\[D(x) = A(x) \times B(x) = x^2 + x^3 + x^4 + x^5\]

となり、さきほどの例示と比較すると \(C(x), D(x)\) は \(\mathcal{A} + \mathcal{B}, \mathcal{A} \times \mathcal{B}\) の母関数になっていることが確認できます。

上の例ではさすがに当たり前すぎて何の役に立つのかよくわからないと思うので、もう少し使い道のありそうな例で考えていきましょう。

高橋君は階段を \(1\) ステップに \(1\) 段または \(2\) 段ずつ進んで登ることにしました。\(N = 0,1,\dots, n\) について、\(N\) 段の階段の登り方は何通りありますか？

「階段を登る方法」を数列として表すと、条件を満たす数列は \(1, 2\) からなる長さ \(0\) 以上の数列になります。よって数え上げる対象からなる集合 \(\mathcal{F}\) は

\[\mathcal{F} = \lbrace \emptyset, (1), (2), (1, 1), (1, 2),(2,1), (2,2), \dots \rbrace\]

のようになります。
ここで、\(\mathcal{F}\) の要素をはじめに \(1\) 段登ったか \(2\) 段登ったかの \(2\) 通りに分類しましょう。すると \(\mathcal{F}\) はある種の再帰的な性質を持っているので

\[ \begin{aligned} &\mathcal{F} \\ &= \lbrace \emptyset \rbrace + \lbrace (1) \rbrace \times \lbrace \emptyset, (1), (2),\dots, \rbrace + \lbrace (2) \rbrace \times \lbrace \emptyset, (1), (2),\dots, \rbrace \\ &= \lbrace \emptyset \rbrace + \lbrace (1) \rbrace \times \mathcal{F} + \lbrace (2) \rbrace \times \mathcal{F} \end{aligned} \]

と記述することができます。

さて、\(\mathcal{F}\) を「段数」に注目した母関数に置き換えてみましょう。段数を \(x\) の指数部分に置き換えると、\(\emptyset\) は \(x^0 = 1\)、\((1)\) は \(x\) 、\((2)\) は \(x^2\) に置き換えられるので、\(\mathcal{F}\) に対応する母関数 \(F(x)\) は

\[ \begin{aligned} &F(x) = 1 + xF(x) + x^2 F(x) \\ &\to F(x) = \frac{1}{1 - x - x^2} \end{aligned} \]

であるとわかります。実際、 \(F(x)\) を級数展開すると

\[F(x) = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + \dots\]

となり、求める数列 \((f_n)\) はフィボナッチ数列

\[ (f_n) = 1, 1, 2, 3, 5, 8, 13, 21, \dots \]

と一致することが確認できます。

2 つの例が意味することとして、結局、母関数とは、数え上げる対象からなる「集合」から、必要な情報 (ここでは価格や段数) 以外を捨象したものになります。
そして、数え上げる対象 が良い性質を持っている場合、 対象からなる集合の大きさは母関数に対する加算や乗算などの初等的な演算で記述できて、計算できる形に持ち込むことができます。このような操作を機械的に行うことができるのが母関数を用いる 1 つの利点となります。

とはいえ母関数解法に過度の信頼を抱くのは禁物で、答えの母関数を得られたとしても、求めたい係数を計算するのに高度なテクニックが必要だったり、係数が容易に計算できない式であったりするケースも少なくないのには注意が必要です。

組合せ的な “構造” と関数の合成

前章で出てきたのは \(+\) と \(\times\) という基本的な演算の \(2\) つのみでしたが、次はもう少し大きな “パーツ” を扱ってみましょう。

数え上げる対象からなる集合は、ある種の組合せ的な “構造” の上に載っていることが多いです。(例：列, 円環, 集合, …) このような構造は、集合から集合への写像 \(\mathrm{C}(\mathcal{A})\) として扱うことができます。

ここで特筆すべき点としては、\(\mathrm{C}\) がどのような関数か分かっていれば、 \(\mathcal{A}\) を \(\mathrm{C}\) に代入することでただちに \(\mathrm{C}(\mathcal{A})\) の集合を描写することができる点にあります。
これを応用すると、数え上げたい対象が複雑な構造をしていても、それがどのような集合の合成で出来ているかを把握することができれば、いくつかの簡単な部品に “分解” して考察を大きく単純化・機械化することができます。

“構造” の簡単な例として、集合 \(\mathcal{A}\) に対して「 \(\mathcal{A}\) の要素からなる長さ \(0\) 以上の列」に対応する構造 \(\mathrm{SEQ}(\mathcal{A})\) を考えてみましょう。列の長さが \(i\) のときは \(\mathcal{A}^i\) になることから、 \(\mathrm{SEQ}(\mathcal{A})\) は\(\mathcal{E}\) を空の列を意味する集合として次のように表すことができます。

\[\mathrm{SEQ}(\mathcal{A}) = \mathcal{E} + \mathcal{A} + \mathcal{A} \times \mathcal{A} + \mathcal{A} \times \mathcal{A} \times \mathcal{A} + \dots = \sum_{i=0}^\infty \mathcal{A}^i\]

これを母関数の世界で言い換えると、無限級数の公式から

\[S(x) = 1 + A(x) + A(x)^2 + \dots = \sum_{i=0}^\infty A(x) = \frac{1}{1 - A(x)}\]

と変形することができます。

構造 \(\mathrm{SEQ}(\mathcal{A})\) をさっそく問題に適用していきましょう。さきほどのフィボナッチ数列の例も \(\mathrm{SEQ}(\mathcal{A})\) に代入することで機械的に求めることができます。「階段の登り方」は長さ \(0\) 以上の登り方の列とみなせて、「階段を \(1\) 段か \(2\) 段登る」という操作 \(\mathcal{A}\) の母関数は

\[A(x) = x + x^2\]

なので、これを上式に代入することで、フィボナッチ数列の母関数 \(F(x)\) は、

\[F(x) = \frac{1}{1 - A(x)} = \frac{1}{1 - x - x^2}\]

であると直ちにわかります。

せっかくなので中身がある例をもう \(1\) 問挙げてみましょう。

今、高橋君は 2D グリッドの \((0,0)\) にいます。
高橋君は \(0 \leq a, 0 \leq b, (a,b) \neq (0,0)\) を満たす整数 \(a, b\) を選んで、\((x,y) \to (x+a,y+b)\) に移動する操作を繰り返します。
\((N, N)\) に移動する方法は何通りですか？

この問題は包除原理を使えば \(\mathrm{O}(N)\) 程度で解けますが、そこまで明らかではないと思います。このような数え上げは母関数を利用することで機械的に答えを求められます。

高橋君の \(1\) 回の移動がどのような “構造” かを考えると、縦軸方向への \(1\) マス移動を \(\mathcal{H}\), 横軸方向への \(1\) マス移動を \(\mathcal{W}\), 移動しないことを \(\mathcal{E}\) として

\[ \begin{aligned} &\mathcal{A} \\ &= (\mathcal{E} + \mathcal{H} + \mathcal{H}^2 + \dots) \times (\mathcal{E} + \mathcal{W} + \mathcal{W}^2 + \dots) - \mathcal{E} \\ &= \mathrm{SEQ}(\mathcal{H}) \times \mathrm{SEQ}(\mathcal{W}) - \mathcal{E} \end{aligned} \]

という構造を取っています。

• ここで何の断りもなく \(-\) が登場していますが、この \(-\) は
  \(\mathcal{C} = \mathcal{A} + \mathcal{B} \iff \mathcal{A} = \mathcal{C} - \mathcal{B}\)
  を満たす演算 、くらいの意味で使っています。

そこで縦軸方向に変数 \(x\), 横軸方向に変数 \(y\) を割り当てた \(2\) 変数の母関数を考えてみると、

\[ \begin{aligned} A(x, y) &= \left(\frac{1}{1 - x}\right) \left(\frac{1}{1 - y}\right) - 1 \\ &= \frac{1}{(1-x)(1-y)}-1 \end{aligned} \]

を得ることができます。求めたい解の構造は明らかに \(\mathcal{A}\) の列 \(\mathrm{SEQ}(\mathcal{A})\) なので、母関数 \(F(x, y)\) は

\[ \begin{aligned} F(x, y) &= \frac{1}{1 - A(x,y)}\\ &= \frac{(1 - x)(1 - y)}{1 - 2x - 2y + 2xy} \end{aligned} \]

であるとわかります。答えは \(F(x,y)\) の \(x^N y^N\) の係数に相当して、あとは

\[ \begin{aligned} &\lbrack x^a y^b \rbrack \frac{1}{1-2x-2y+2xy} \\ &= \sum_{i=0}^\infty (2xy-2x-2y)^i \\ &= \sum_{i=\max(a,b)}^{a+b} \binom{i}{a+b-i,i-a,i-b} 2^i (-1)^{b-a} \end{aligned} \]

なのを利用すれば \(\mathrm{O}(N)\) で答えを求められます。

このように数え上げる対象がいくつかの “構造” の組み合わせでできているとき、それらの “構造” 一つ一つの関数さえわかっていれば、それらを組み合わせて関数を合成することで数え上げる対象の母関数をただちに求めることができます。

多重集合の “構造”

さて、このままだとこの記事は H 問題の editorial としての役割を果たさずに終わってしまいそうなので、 H 問題を解くために多重集合の構造について考えてみましょう。

以下では次の事実を示します。

構造 \(\mathrm{MULTISET}(\mathcal{A})\) を \(\mathcal{A}\) の要素からなる多重集合を意味する構造とする。

\[\mathcal{B} = \mathrm{MULTISET}(\mathcal{A})\]

であるとき、\(\mathcal{A}, \mathcal{B}\) の母関数を \(A(x), B(x)\) とすると

\[B(x) = \exp \left(\sum_{0 \lt k} \frac{A(x^k)}{k} \right)\]

が成り立つ。

これを数え上げの世界の言葉に直すと、次のようになります。

今、たくさんのボールがあり、重さが \(w\) であるボールが \(a_w\) 種類あるとする。同じ種類のボール同士は区別できない。
ボールをいくつか袋に詰めることを考える。 このとき、重みの和が \(w\) になるような袋の詰め方 \(b_w\) を求めたい。
\(a_w, b_w\) の母関数を \(A(x), B(x)\) としたとき、\(A(x)\) と \(B(x)\) の関係式は

\[B(x) = \exp \left(\sum_{0 \lt k} \frac{A(x^k)}{k} \right)\]

になる。

つまり、 \(\mathrm{MULTISET}\) は重複組み合わせを表現するのに使う “構造” ということになります。

母関数 \(B(x)\) を導出する方法はいくつかありますが、まずは上で紹介した “構造” を使う方法を示します。

まずは簡単のためすべてのボールが重み \(1\) の場合を考えてみましょう。このとき、求める母関数は重複組み合わせ \(\ _n H_r\) の \(r\) を固定したときの母関数となります。

\(r\) 種類のボールに対応する構造を \(\mathcal{C}_1, \mathcal{C}_2, \dots, \mathcal{C}_r\) のように表します。求める構造は「\(\mathcal{C}_1\) から \(0\) 個以上を選び、\(\mathcal{C}_2\) から \(0\) 個以上を選び、…」という形になるので、式に表すと

\[ \begin{aligned} &(\mathcal{E}+\mathcal{C}_1+\mathcal{C}_1^2 + \dots) \\ &\times (\mathcal{E}+\mathcal{C}_2+\mathcal{C}_2^2 + \dots) \\ &\vdots \\ &\times (\mathcal{E}+\mathcal{C}_r+\mathcal{C}_r^2 + \dots) \\ &= \prod_{i=1}^r \sum_{j=0}^\infty \mathcal{C}_i^j \end{aligned} \]

のような形になります。

これを個数の情報のみを取り出した母関数に置き換えると、 \(\mathcal{C}_1,\dots,\mathcal{C}_r\) はすべて \(x\) に置き換えられるので全体で

\[ \frac{1}{(1-x)^r} = \sum_{i=0}^\infty \binom{r + i - 1}{r - 1} x^i\]

になるのがわかります。(上式は重複組み合わせの公式と確かに一致します。)

一般の場合に拡張しましょう。重み \(k\) のボールに対応する構造を \(\mathcal{D}_k\) とすると、上の議論を用いて

\[\mathcal{B} = \prod_{0 \lt k} \left( \sum_{i=0}^\infty \mathcal{D}_k \right)^{a_k}\]

となります。ここから個数の情報だけを取り出して母関数で表すと、 \(\mathcal{D}_k\) は \(x^k\) に置き換えられるので

\[ B(x) = \prod_{0 \lt k} \left(\frac{1}{1-x^k}\right)^{a_k}\]

を得ることができます。

ここから先はテクニックの話です。 \(\exp \log\) テクと呼ばれる FPS 典型テクニックがあって、これを用いると

\[ \begin{aligned} &B(x) \\ &= \exp \log B(x) \\ &= \exp \sum_{0 \lt k} -a_k \log (1 - x^k) \\ &= \exp \sum_{0 \lt k} a_k \sum_{0 \lt i} \frac{x^{ik}}{i}\\ &= \exp \sum_{0 \lt i} \frac{1}{i} \sum_{0 \lt k} a_k (x^i)^k\\ &= \exp \left(\sum_{0 \lt i} \frac{A(x^i)}{i} \right) \end{aligned} \]

となり、求める式を得ることができました。

もう一つの方法としてポリアの定理を使う方法が挙げられます。そちらも面白いので紹介していきましょう。

まず、袋に入れるボールの個数が \(n\) 個の場合に固定して、そのときの場合の数の母関数 \(B_n(x)\) を考えます。\(B(x) = \sum_n B_n(x)\) なので、全ての \(n\) に対して \(B_n(x)\) を足し合わせたものが求まればよいです。
ポリアの定理より、 \(n!\) 通りの置換に対しての不動点の個数を足し合わせて \(n!\) で割ったものが答えになるのでそれを求めます。ABC226F と同様に巡回置換の長さの多重集合ごとに分けて数え上げると、長さ L の置換があるときの寄与は

• 袋の詰め方→長さ \(L\) の置換では \(L\) 個 が全く同じ状態なので \(A(x)^L\)
• 巡回置換 → \((L-1)!\) 通り

なので、置換 \(p\) を長さ \(L_i\) の巡回置換が \(F_i\) 個ある多重集合とみなして \((L_1, F_1),(L_2, F_2),\dots\) の組として表したとき、多重集合 \(s\) に対応する不動点の個数の母関数 \(E_s(x)\) は

\[ \begin{aligned} &B_s(x) \\ &= n! \cdot \prod_{(L,F) \in s} \frac{A(x^L)・((L-1)!)^F }{(L!)^F・F!} \\ &= n! \cdot \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!} \\ \end{aligned} \]

となります。

\(B_s(x)\) を用いて \(B_n(x)\) を表すと、要素の和が \(n\) である多重集合からなる集合を \(S_n\) として

\[ \begin{aligned} &B_n(x) \\ &= \frac{1}{n!} \sum_{s \in S_n} B_s(x) \\ &= \frac{1}{n!} \sum_{s \in S_n} n! \cdot \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!} \\ &= \sum_{s \in S_n} \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!} \end{aligned} \]

となり、式から \(n\) が消えていることがわかります。 (はじめの \(\frac{1}{n!}\) はポリアの定理より \(n!\) で割る部分に対応しています。)
よって、求めたい答え \(B(x)\) はすべての多重集合 \(s\) に対して \(\frac{B_s(x)}{n!}\) を足し合わせたもので、

\[ \begin{aligned} &B(x) \\ &= \sum_s \prod_{(L,F) \in s} \frac{(A(x)/L)^F}{F!} \\ \end{aligned} \]

となり、上の式を \(L\) に対してまとめると

\[ \begin{aligned} &B(x) \\ &= \prod_{0 \lt L} \left( 1 + \frac{A(x)}{L} +\frac{1}{2!} \left(\frac{A(x)}{L}\right)^2 + \frac{1}{3!} \left(\frac{A(x)}{L}\right)^3 + \dots \right) \\ &= \prod_{0 \lt L} \exp \left(\frac{A(x^L)}{L}\right) \\ &= \exp \left(\sum_{0 \lt L} \frac{A(x^L)}{L} \right)\\ \end{aligned} \]

を得ることができました。

解法

さて、下準備が整ったところでさっそく問題の解説へ入っていきましょう。

まずは簡単のため、集合を使って問題を記述していきましょう。

• 「空でない袋」に対応する集合を \(\mathcal{F}\)
• 「金塊」に対応する集合を \(\mathcal{G}\)
• 「袋」を \(\mathcal{B}\)
• 「何もない」ということを \(\mathcal{E}\)

とおきます。すると、問題文に与えられている制約は \(\mathcal{B}, \mathcal{E}, \mathcal{F}, \mathcal{G}\) を用いて

\[ \mathcal{F} = \mathcal{B} \times \left( \mathrm{MULTISET} (\mathcal{F} + \mathcal{G}) - \mathcal{E} \right)\]

と記述できるのがわかります。

さて、これを重さ以外の情報を捨象した母関数に言い換えましょう。
答えとなる母関数を \(F(x)\)、金塊 1 個の母関数を \(G(x) = \sum_{1 \leq i \leq K} x^{w_i}\) とおきます。(ここで \(F(x)\) は \([x^0]F(x) = [x^1]F(x) = 0\) を満たします。) すると、集合は次のように母関数に置き換えることができます。

\[\mathcal{B} \to x, \mathcal{E} \to 1, \mathcal{F} \to F(x), \mathcal{G} \to G(x)\]

よって \(H(x) = F(x) + G(x)\) とおくと、\(F(x)\) と \(H(x)\) の間には

\[F(x) = x \left( \exp \left(\sum_{0 \lt k} \frac{H(x^k)}{k} \right) - 1\right)\]

という関係式が成り立つことが前章の導出により確認できます。

ここまでは考察の部分で、ここからはテクニックの話です。この式をどうにか高速に計算できる形に持っていきましょう。

こういう問題ではやはり両辺を微分して漸化式を求めるのが典型です。

\[F(x) = x \left( \exp \left(\sum_{0 \lt k} \frac{H(x^k)}{k} \right) - 1\right)\]

の両辺を微分して \(x\) を掛けると

\[xF'(x) = F(x) + (F(x) + x) \sum_{0 \lt k} x^{k} H'(x^k)\]

を得ることができます。ここで、

\[F^{\ast}(x) := \sum_k k f_k x^k\]

のように定義して上の式を見やすくすると

\[F^\ast(x) = F(x) + (F(x) + x) \sum_{0 \lt k} H^\ast(x^k)\]

と表せます。\(n \geq 2\) に対して \(J(x) := \sum_{0 \lt k} H^\ast(x^k)\) として \(F(x), J(x)\) の \(n\) 次の係数を \(f,j\) で表すと、

\[ \begin{aligned} n f_n &= f_n + j_{n-1} + \sum_{0 \lt k \lt n} f_k j_{n-k} \\ \to f_n &= \frac{1}{n - 1} \left(j_{n-1} + \sum_{0 \lt k \lt n} f_k j_{n-k}\right) \end{aligned} \]

となります。 (\(f_0 = j_0 = 0\) を使いました) また、\(j_n\) の各係数は

\[ \begin{aligned} &j_n \\ &= \sum_{k | n} [x^n] H^\ast(x^k) \\ &= \sum_{k | n} [x^\frac{n}{k}] H^\ast(x) \\ &= \sum_{k|n} \frac{n}{k}(f_{\frac{n}{k}} + g_{\frac{n}{k}}) \\ &= \sum_{d|n} d (f_d + g_d) \\ \end{aligned} \]

と表せるので \(f_0, \dots, f_n\) が求まっていれば計算できます。
以上より二つの式を合わせると、分割統治 FFT で \(f_n, j_n\) の列が \(\mathrm{O}(N \log^2 N)\) で求まります。よってこの問題を十分高速に解くことができました。

• \(j_n\) は \(f_0, \dots, f_n\) に依存しているので、ABC213H と同様の分割統治だと上手くいかず、遷移のタイミングを工夫する必要があるのに注意してください。(わからない人のためのヒント : \(L = 0\) とそれ以外で場合分け)

なお、多項式のニュートン法を用いて \(\mathrm{O}(N \log N)\) でこの問題を解くこともできますがここでは割愛します。

発展問題：unlabeled tree の数え上げ

OEIS のトップページへ行くと、検索欄に数列の例として

\[1,2,3,6,11,23,47,106,235\]

という数列が並んでいると思います。これは OEIS A000055 の冒頭部分で、 \(N\) 頂点の unlabeled tree の個数に関する数列になっています。
実はこの問題の解法は unlabeled tree の数え上げに出てくる手法を取り上げたものとなっています。というわけで、 \(N\) 頂点の unlabeled tree の個数を \(998244353\) で割ったあまりを \(\mathrm{O}(N \log^2 N)\) で求めてみましょう。