AtCoder Beginner Contest 011 D - 大ジャンプ

D - 大ジャンプ

時間制限 : 2sec / メモリ制限 : 256MB

問題文

XY 座標上に、スタート地点とゴール地点が 1 つずつあります。 スタート地点は (0,0) にあり、ゴール地点は (X,Y) です。

あなたは、ジャンプという移動法を用いて、移動を行います。 ジャンプを 1 回行うと、あなたは、以下の 4 つのうち、ランダムで選ばれた 1 つの移動が行われます。

X 軸に平行に +D だけ移動する。 X 軸に平行に −D だけ移動する。 Y 軸に平行に +D だけ移動する。 Y 軸に平行に −D だけ移動する。 これらの移動は、どれもちょうど 1⁄4 の確率で選択されます。

あなたは、最初にスタート地点におり、ちょうど N 回のジャンプでゴール地点にたどり着きたいです。

目的を達成できる確率を出力しなさい。

note

nCkをパスカルの三角形とかで求める。x軸の正の方向にa回、x軸の負の方向にb回、y軸の正の方向にc回、x軸の負の方向にd回、移動するときにゴール地点にたどりつけるとすると、実は、N回のうち、x軸方向の移動に何回使うかをきめるとこの4つの変数が確定する.一つの変数を固定すると、他の変数も決まるあるあるのやつである。ただし、場合の数を全部求めて最後4ⁿでわってあげれば終わりかというと、4ⁿが大きすぎて、余裕で浮動小数点数の精度が制約をみたせない。そこでnCkの値を初めからnCk/2ⁿの値にしておき、精度の低下を防ぐ。 精度のせいでwaに何度もなって発狂しそうになった。