スコルの知恵袋

主にプログラミング関係の気になったこと等をまとめたブログ

鹿島建設プログラミングコンテスト2020 (ARC110) の D 問題を形式的冪級数を使って解く

競プロひとくちメモ

これは鹿島建設プログラミングコンテスト2020 (ARC110) の D 問題を形式的冪級数を使って解くためのメモ

問題

形式的冪級数を使って解く

サーバル「D問題は……えーっと、最近はやってる形式的べき級数ってやつででFi(X)=ΣC(k,Ai)X^kとするとΠFiのk次の係数が「和がkのとき」の答えになって、Fi=X^Ai/(1-X)^(Ai+1)だから頑張って計算するとC(N+M,N+ΣAi)になることがわかるよ！！」
— 競技プログラミングをするフレンズ (@kyopro_friends) December 5, 2020

kyopro_friends さんのこの(↑)ツイートを参考にする。ツイートで述べられているように

$\displaystyle{ \begin{align} F_{i}(x) &= \sum_{k=0}^{\infty} \binom{k}{A_{i}} x^{k} \\ G(x) &= \prod_{i=1}^{N} F_{i}(x) \end{align} }$

とおくと、 $G$ の $x^{K}$ の係数が $B_{1} + B_{2} + \cdots + B_{N} = K$ のときの答えとなっている。

この記事より、数列 $\binom{0}{k}, \binom{1}{k}, \binom{2}{k}, \ldots$ の母関数は

$\displaystyle{ \sum_{n=0}^{\infty} \binom{n}{k} x^{n} = \frac{x^{k}}{(1-x)^{k+1}} }$

であって、これを使うと $G$ は次のように整理できる。

$\displaystyle{ \begin{align} G(x) &= \prod_{i=1}^{N} \left\{ \sum_{k=0}^{\infty} \binom{k}{A_{i}} x^{k} \right\} = \prod_{i=1}^{N} \frac{x^{A_{i}}}{(1-x)^{A_{i} + 1}} = \frac{x^{S}}{(1-x)^{S+N}} \\ &= x^{S} \sum_{k=0}^{\infty} \binom{k+S+N-1}{k} x^{k} \quad (S = \sum_{i=1}^{N} A_i) \end{align} }$

求める答えは $G$ の $x^0, x^1, \ldots, x^M$ の係数の和だから

$\displaystyle{ \begin{align} \mathrm{ans} = \sum_{k=0}^{M-S} \binom{k+S+N-1}{k} = \binom{M + N}{M - S} = \binom{M + N}{S + N} \end{align} }$

となる。第 2 式から第 3 式への変形では次の関係を使った。

$\displaystyle{ \begin{align} \sum_{k=0}^{m} \binom{n+k}{k} = \binom{n + m + 1}{m} \end{align} }$

これは数学的帰納法や WolframAlpha を使うことで証明できる。また、この式が正しいことはパスカルの三角形からも読み取ることができる。

[追記]

maspy さんのブログを読むと $G$ の $x^0, x^1, \ldots, x^M$ の係数の和は上の関係式を使わなくても求められることが分かる。

数列 $A_0, A_1, A_2, \ldots$ に対して $S_k = A_0 + \cdots + A_k$ とおいて、これらの母関数を

$\displaystyle{ \begin{align} f_A(x) &= \sum_{i = 0}^{\infty} A_{i} x^{i} \\ f_S(x) &= \sum_{i = 0}^{\infty} S_{i} x^{i} \end{align} }$

とおく。ここで、

$\displaystyle{ \begin{align} (A_0 + A_1 x + A_2 x^2 + \cdots) (1 + x + x^2 + \cdots) = S_0 + S_1 x + S_2 x^2 + \cdots \end{align} }$

が成り立つことから、

$\displaystyle{ \begin{align} f_S (x) = \frac{f_A (x)}{1 - x} \end{align} }$

という関係が得られる。つまり、数列 $A$ の累積和 $S$ の母関数は数列 $A$ の母関数を $1-x$ で割るだけで得られる！(すごい)

この事実をつかうと、求める答えは $(1-x)^{-1} G$ の $x^M$ の係数ということになるから

$\displaystyle{ \begin{align} \frac{1}{1-x} G(x) = \frac{x^S}{(1-x)^{S+N+1}} = x^S \sum_{k=0}^{\infty} \binom{k + S + N}{k} x^{k} \end{align} }$

より、

$\displaystyle{ \begin{align} \mathrm{ans} = \binom{(M-S) + S + N}{M-S} = \binom{M + N}{M - S} = \binom{M + N}{S + N} \end{align} }$

感想

FPS 強ぇ～～

使えるようになりたいね。

[追記]

$1-x$ で割ったら累積和になるとかいうの、ラプラス変換で $s$ で割ったら積分になるのと似てるなとか思った。