第一回日本最強プログラマー学生選手権予選 F. Candy Retribution

これ1000点じゃないだろ

問題概要

読んで: F - Candy Retribution

解法

条件を満たす昇順の列 \displaystyle{\{A_n\}}に対して、それを並べる方法は\displaystyle{\frac{n!}{\prod_k n_k!}}通りある。 ここで\displaystyle{n_k}は \displaystyle{\{A_n\}}に\displaystyle{k}が\displaystyle{n_k}個含まれることを指す。

よって、dp[x][y] := 「y個からなる列を考えた時、それらの和はxとなっているものの並べ方の総数」とした時、それをFPSで表わすなら

\displaystyle{ f_k = \left (1 + \frac{1}{1!}yx^ k + \frac{1}{2!}(y x^ k)^ 2 + \ldots \right ) = e^{yx^k} }

として

\displaystyle{ \prod_{k} f_k = e^ {y \sum_{k} x^ k} = e^ {\frac{y}{1-x}} }

となる。 さて、ここに「M番目とM+1番目の値が同一」という条件を追加する。当然これは扱いづらいので、余事象を考えることにする。 すなわち、

\displaystyle{ \sum_{k=1}^\infty \left \{ [y^ M] \left (\prod_{j=k}^\infty f_j \right ) \cdot [y^ {N-M}] \left (\prod_{j=0}^{k-1} f_j - \prod_{j=0}^{k-2} f_j \right ) \right \} }

ここで、\displaystyle{ [ y^ n ] f}は\displaystyle{x, y}に関するFPS \displaystyle{f}の\displaystyle{y^ n}の含まれる項の係数を全て取り出し、\displaystyle{x}に関するFPSを作る操作を指す。つまり、具体的な式として書けば

\displaystyle{ \frac{1}{n!} \frac{d^ n}{d y^ n} f {\bigg|_{y=0}} }

である。さて上記の余事象の式を変形していくと

\displaystyle{ \sum_{k=1}^\infty \left \{ [y^M] e^ {y \frac{x^ k}{1 - x}} \cdot [y^{N-M}] (e^ {y \frac{ 1 - x^ k}{1 - x}} - e^ {y \frac{ 1 - x^ {k-1}}{1 - x}}) \right \} \\ = \frac{1}{M!} \frac{1}{(N-M)!} \sum_{k=1}^\infty \left ( \frac{x^ k}{1 - x} \right ) ^M \cdot \left (\left (\frac{ 1 - x^ k}{1 - x} \right ) ^{N-M} - \left (\frac{ 1 - x^ {k-1}}{1 - x} \right) ^{N-M} \right) \\ = \frac{1}{M!} \frac{1}{(N-M)!} \frac{1}{(1-x) ^N} \sum_{k=1}^\infty x^ {Mk} \cdot \left (\left ( 1 - x^ k \right ) ^{N-M} - \left ( 1 - x^ {k-1} \right) ^{N-M} \right) \\ = \frac{1}{M!} \frac{1}{(N-M)!} \frac{1}{(1-x) ^N} \sum_{k=1}^\infty x^ {Mk} \left ( \sum_{j=0}^{N-M} \begin{pmatrix} N-M \\ j \end{pmatrix} (-1)^ j \left (x^ {jk} - x^ {j(k-1)} \right ) \right ) \\ = \frac{1}{M!} \frac{1}{(N-M)!} \frac{1}{(1-x) ^N} \sum_{j=0}^{N-M} \begin{pmatrix} N-M \\ j \end{pmatrix} (-1)^ j \left (\sum_{k=1}^\infty x^ {M k + j k } - \sum_{k=1}^\infty x^ {M k + j k - j} \right ) }

となる。欲しいのは \displaystyle{ [ y^ N ] e^ {\frac{y}{1-x}} = \frac{1}{n!} \frac{1}{(1-x)^ N}} と上記の式の \displaystyle{L}項目から\displaystyle{R}項目。 \displaystyle{\frac{1}{1-x}}を掛けて累積和を取っておけば、\displaystyle{L-1}項と\displaystyle{R}項の2項を得るだけでよく、上記式をよくにらめば愚直に計算しても調和級数になっているから計算できて、解ける。

これは何？笑