yukicoder No.940 ワープ ε=ε=ε=ε=ε=│;p>д＜│
問題
愚直解
まず、 $ N = X + Y + Z $ とすると、$ N = 0 $ のとき、答えは$ 1 $。そうでないときを考える。
愚直なDPを考えてみる。
$ dp [ x ] [ y ] [ z ] $ を、$ (x, y, z) $ についての答えとする。
この値は、 $ i \le x, j \le x, k \le x $ となる $ (i, j, k) \ne (x, y, z) $ に対する $ dp \lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack$ を足したもの。
これに自身を足すと、 $ 2 dp\lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack = \displaystyle \sum_{i \le x} \sum_{j \le y} \sum_{k \le z} dp\lbrack i \rbrack \lbrack j \rbrack \lbrack k \rbrack$ がわかる。これは、累積和がdp配列からわかることをいっている。
これを使うと、累積和を使った $ \Theta (XYZ) $ のDPが思いつく。
\[ dp [x][y][z] = 2 \sum_{i \in \lbrace 0, 1 \rbrace } \sum_{j \in \lbrace 0, 1 \rbrace } \sum_{k \in \lbrace 0, 1 \rbrace } (-1)^{i+j+k} dp \lbrack x-i \rbrack \lbrack y-j \rbrack \lbrack z-k \rbrack \]
形式的冪級数による式変形
このままの貰うDPでは扱いにくいので、配るDPにしてみると、次の形になる。
\[ dp [ x+i ] [ y+j ] [ z+k ] \mathrel{{+}{=}} 2 \cdot (-1)^{i+j+k} dp \lbrack x \rbrack \lbrack y \rbrack \lbrack z \rbrack \quad (i, j, k \in \lbrace 0, 1\rbrace) \]
これで、形式的冪級数が適用できそうになる。
変数 $ x, y, z$ を使うと、配るという操作は、$ f(x, y, z) =2(1 - (1-x)(1-y)(1-z)) $ をかける動作になる。
最終的な解は、操作回数ごとに和を取ることで、$ \displaystyle \sum_{i = 0}^{N} f^{i} $ の $ x^{X} y^{Y} z^{Z} $ の係数 ということができる。
$ \displaystyle \sum_{i = 0}^{N} f^{i} $ を二項定理を使って変形する。
\[ = \sum_{i = 0}^{N} 2^{i} \sum_{j = 0}^{N} \binom{i}{j} (-1)^{j} (1-x)^{j} (1-y)^{j} (1-z)^{j} \]
$ x^{X} y^{Y} z^{Z}$ の係数を取り出すと、
\[ = \displaystyle \sum_{i = 0}^{N} 2^{i} \sum_{j = 0}^{N} \binom{i}{j} (-1)^{N+j} \binom{j}{X} \binom{j}{Y} \binom{j}{Z} \]
\[ = \displaystyle \sum_{j = 0}^{N} (-1)^{N+j} \binom{j}{X} \binom{j}{Y} \binom{j}{Z} \sum_{i = 0}^{N} 2^{i} \binom{i}{j} \]
とだいぶ扱いやすい形になる。
この式の前半部分は階乗前計算で $ \Theta(1) $ で可能。
後半部分に二項定理を使う。( $ t^{j} $ の係数が上の式でいう $ j $ と対応している )
\begin{eqnarray} &\sum_{i = 0}^{N} 2^{i} \sum_{j = 0}^{N} \binom{i}{j} t^{j} \\ =& \sum_{i = 0}^{N} (2+2t)^{i} \\ =& \frac{ (2+2t)^{N+1} - 1}{(2+2t) - 1} \\ =& \frac{ (2+2t)^{N+1} - 1}{1+2t} \end{eqnarray}
分子は二項定理で$\Theta(N) $で求まり、$1 + 2 t $ で割る操作も戻すDPで$ \Theta(N) $ でできるので、全体で$\Theta(N) $で解けた。
ACコード
最後に
むずかしい