ABC240 G - Teleporting Takahashi - かんプリンの学習記録

形式的冪級数を用いた解法です．

問題概要
解説
提出プログラム
感想

問題概要

三次元グリッドのマス ${(0,0,0)}$ から隣り合う6つのマスのうち，いずれかのマスへの移動をちょうど ${N}$ 回行った後にマス ${(X,Y,Z)}$ にいるような移動経路数を求めよ．

${1\leq N\leq 10^7}$
${-10^7\leq X,Y,Z\leq 10^7}$

解説

移動の仕方は対称なので ${X,Y,Z\leq 0}$ であるものとします．

答えは ${[x^{X}y^{Y}z^{Z}](x+x^{-1}+y+y^{-1}+z+z^{-1})^N}$ です．このままだと負冪がありますが， ${(xyz)^N}$ 等をかけると形式的冪級数になります．今回は元の式のまま変形していきます(多分問題ないはず)．

${[x^{X}y^{Y}z^{Z}](x+x^{-1}+y+y^{-1}+z+z^{-1})^N\\ = [x^{X}y^{Y}z^{Z}]( (x+y)(1+(xy)^{-1})+(z+z^{-1}) )^N\\ = \displaystyle[x^{X}y^{Y}z^{Z}]\sum_{k=0}^{N}\binom{N}{k}(x+y)^k(1+(xy)^{-1})^k(z+z^{-1})^{N-k}\\}$

${x,y}$ に着目すると，
${\displaystyle[x^{X}y^{Y}]\left(\sum_{s=0}^{k}\binom{k}{s}x^{s}y^{k-s}\right)\left(\sum_{t=0}^{k}\binom{k}{t}(xy)^{-t}\right)\\ =\displaystyle[x^{X}y^{Y}]\sum_{s,t}\binom{k}{s}\binom{k}{t}x^{s-t}y^{k-s-t}}$
${ \left\{ \begin{array}{ll} s-t=X\\ k-s-t=Y \end{array} \right. }$ より， ${ \left\{ \begin{array}{ll} s=\frac{k+X-Y}{2}\\ t=\frac{k-X-Y}{2} \end{array} \right. }$ となります．

${z}$ に着目すると，
${\displaystyle[z^{Z}]\sum_{t=0}^{N-k}\binom{N-k}{t}z^{t-(N-k-t)}\\ =\displaystyle[z^{Z}]\sum_{t=0}^{N-k}\binom{N-k}{t}z^{t-(N-k-t)}}$
${2t-N+k=Z}$ より， ${t=\frac{N-k+Z}{2}}$ となります．

以上のことから，答えは ${\displaystyle\sum_{k=0}^{N}\binom{N}{k}\binom{k}{\frac{k+X-Y}{2}}\binom{k}{\frac{k-X-Y}{2}}\binom{N-k}{\frac{N-k+Z}{2}}}$ です．
これは二項係数の前計算のもと ${O(N)}$ で求められます．ただし，二項係数 ${\displaystyle\binom{n}{k}}$ は ${n,k}$ が ${0\leq k\leq n}$ を満たす整数でないとき ${0}$ であるものとします．