ABC#011 D.大ジャンプ

その他 参加ログ

問題

XY座標の原点からゴール(X,Y)までジャンプで移動する。
ジャンプは、X,Y軸に平行に上下左右のどれかにDだけランダムに移動する。その確率は1/4。
ちょうどN回ジャンプしたときにゴール地点にいる確率を求めよ。

1<=N<=1000
1<=D<=10^9
-10^9 <= X,Y <= 10^9

考え方

まず、X,Yはそれぞれ絶対値をとっても問題ない。


XとYがそれぞれDで割り切れないといけない。
XとYをそれぞれDで割ったものがゴールへの最短回数になるが、今回はN回ちょうどでなければならない。

Nを、上下方向にn回、左右方向にm(=N-n)回使ったと仮定する。
y=Y/Dとすると、n回でyにならないといけないので、上にup回、下にdown回とすると、up-down=yかつup+down=nでないといけない。
なので、このとき、up=(y+n)/2回、down=n-up回動くことになる。
左右についても、right=(x+m)/2回、left=m-right回動くことになる。
(upやrightの計算の時、2で割って割り切れないといけないことに注意)


このときの確率は、(1/4)^N * Comb(N, up+down) * Comb(up+down, up) * Comb(right+left, right)になる。
nをN回分回して計算すればよい。


また、(1/4)^1000とかはdoubleの精度を超えるので、logとって計算するなどが必要。