Official

Ex - Flipping Coins 2 Editorial by Nyaan


想定解と少し異なる方法で答えを導出する方法を説明します。
いくらかの言い換えにより、結局、ある列 \(C_0, C_1, \dots, C_N\) に対して

\[dp_{0,0} = 1,dp_{i,j} = dp_{i-1,j-1} + (C_i + j) dp_{i-1,j}\]

としたときの \(dp_{N,\ast}\) を列挙できればよいです。\(dp_{i,j}\) の母関数を \(F_i(x)\) として、DP を母関数の関係式に直すと

\[F_0 = 1, F_i = \left(x + C_i + x\frac{d}{dx} \right) F_{i-1}\]

です。 \(X = x + x \frac{d}{dx}, S_i(x) = \sum_{j=0}^i {i \brace j}x^j\) とおくと、\(\left(x+x\frac{d}{dx}\right)^n (1)= S_n(x)\) なのを利用すると \(F_N(x)\)

\[ \begin{aligned} F_N(x) &= \left(\prod_j (X+C_j)\right) F_0(x)\\ &= \sum_{i=0}^N \left(\lbrack x^{i} \rbrack \prod_j(x+C_j)\right) X^i (1)\\ &= \sum_{i=0}^N \left(\lbrack x^{i} \rbrack \prod_j(x+C_j)\right) S_i(x) \end{aligned} \]

と変形できます。
上式を行列で表現してみましょう。\(d_i = \lbrack x^{i} \rbrack \prod_j(x+C_j)\) とすると、\(F_N(x)\) の係数 \(f_0, f_1, \dots, f_N\) は横ベクトル \(d = (d_0, d_1, ..., d_N)\) にスターリング 行列 \(S = (s_{i,j} = {i \brace j})\) を作用させれば計算できます。つまり \(\bold{f} = \bold{d}S\) です。

恒等式

\[{i \brace j}= \frac{1}{j!} \sum_{k=0}^j (-1)^{j-k} \binom{j}{k}k^i\]

を利用すると、ヴァンデルモンド行列 \(V\), 上三角パスカル行列 \(P\) , 対角成分が階乗の逆元である対角行列 \(M\)

\[V = (v_{i,k} = k^i)\]

\[P = \left(p_{k,j} = \binom{j}{k}\right)\]

\[P^{-1} = \left(p'_{k,j} = (-1)^{j-k}\binom{j}{k}\right)\]

\[M = \left(m_{i,j} = \frac{\delta_{i,j}}{j!} \right)\]

としたとき(\(\delta\) はクロネッカーのデルタ)

\[S = V P^{-1} M\]

になるので

\[\bold{f} = \bold{d} V P^{-1} M\]

となり、横ベクトルに \(V, P^{-1}\) を高速に作用できればよいとわかります。横ベクトルに \(V\) を作用させるのは multipoint evaluation で \(\mathrm{O}(N \log^2 N)\) , \(P\) は包除+畳み込み の要領で \(\mathrm{O}(N \log N)\) で計算できるので、\(F_N(x)\)\(\mathrm{O}(N \log^2 N)\) で求められます。

また、以上の考察から multipoint evaluation を利用しない解法の存在も確認できます。答えは ある縦ベクトル \(\bold{v}^T\) および行列 \(M'\) を用いて \(\bold{d} S M' \bold{v}^T\) と表せます。これを \(\bold{d}\) を起点に左から計算したのが上記の解法ですが、逆に右から計算すれば multipoint evaluation を回避できるのは明らかです。 ( \(P, M'\) やその転置 / 逆行列の作用はすべて 包除+畳み込み の要領で \(\mathrm{O}(N \log N)\) で計算できます。また、\(V\) の縦ベクトルへの作用は ABC259-Ex で出題した方法で \(\mathrm{O}(N \log^2 N)\) で計算出来て定数倍も比較的軽いです。)

posted:
last update: