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) $$ に対する を足したもの。
これに自身を足すと、 $$ 2 dp[x][y][z] = \displaystyle \sum_{i \le x} \sum_{j \le y} \sum_{k \le z} dp[i][j][k] $$ がわかる。これは、累積和がdp配列からわかることをいっている。
これを使うと、累積和を使った $$ \Theta (XYZ) $$ のDPが思いつく。
\[ dp [x][y][z] = \displaystyle 2 \sum_{i \in \{ 0, 1 \} } \sum_{j \in \{ 0, 1\} } \sum_{k \in \{ 0, 1 \} } (-1)^{i+j+k} dp [ x-i ] [ y-j ] [ z-k ] \]
形式的冪級数による式変形
このままの貰う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} $$ を二項定理を使って変形する。
$$ \displaystyle = \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 $$ と対応している )
$$ \displaystyle \sum_{i = 0}^{N} 2^{i} \sum_{j = 0}^{N} \binom{i}{j} t^{j} $$
$$ \displaystyle = \sum_{i = 0}^{N} (2+2t)^{i} $$
$$ \displaystyle = \frac{ (2+2t)^{N+1} - 1}{(2+2t) - 1} $$
$$ \displaystyle = \frac{ (2+2t)^{N+1} - 1}{1+2t} $$
分子は二項定理で$$\Theta(N) $$で求まり、$$1 + 2 t $$ で割る操作も戻すDPで$$ \Theta(N) $$ でできるので、全体で$$\Theta(N) $$で解けた。
ACコード
最後に
むずかしい
