No.011 D

まず $X, Y$ はともに $D$ の倍数でなければ到達できないので確率は $0$ である.

以下 $X, Y$ は $D$ で割っておき, 1回のジャンプでの移動距離を $1$ とする.

$N$ 回の移動のうち, 上下左右への移動の回数をそれぞれ $u, d, l, r$ とすると,

$$\begin{align} u + d + l + r &= N \\ u - d &= Y \\ l - r &= X \end{align}$$

となり, $u$ を定数と考えると,

$$\begin{align} d &= u - Y \\ l &= \frac{N - 2u + X + Y}{2} \\ r &= \frac{N - 2u - X + Y}{2} \end{align}$$

となる. $d, l, r$ が非負整数でない場合はそのような $u$ はとりえない.

$u, d, l, r$ が決まったとき, このような組み合わせになる確率は,

$$\frac{ {}_NC_u \cdot {}_{N-u}C_d \cdot {}_{N-u-d}C_l }{ 4^N }$$

となる. これを $0 \leq u \leq N$ の範囲で計算し, すべてを足す.

なお, 階乗はあらかじめ計算しておけば高速化できる.