D - 大ジャンプ AtCoder Beginner Contest 011

D - 大ジャンプ
問題概略
x軸、Y軸に平行に、Dだけ+かー動ける。N回移動した時、ある地点にたどり着く確率を求めよ

解法
パスカルの三角形を用いればn個の内r個がoである確率が求められる。
今回の場合状態が4つあり、全体Nの内a,b,c,dを選ぶ確率は(N,a+b)*(a+b,a)*(c+d,c)のように2つのパートに分け計算すればよい。

 public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        D = ni();
        X = abs(ni());
        Y = abs(ni());
        if (X % D != 0 || Y % D != 0) {
            System.out.println("0");
            return;
        }
        if (X / D + Y / D > N) {
            System.out.println("0");
            return;
        }
        int nx = 0, ny = 0;
        nx = X / D;
        ny = Y / D;
        int rem = N - nx - ny;
        if (rem % 2 == 1) {
            System.out.println("0");
            return;
        }
        double goal = 0;
        for (int x = 0; x < rem + 1; x += 2) {
            int rx = nx + x / 2;
            int lx = x / 2;
            int uy = ny + (rem - x) / 2;
            double par = ncrPer(N, rx + lx) * ncrPer(rx+lx, rx) * ncrPer(N - rx - lx, uy);
            goal += par;
        }
        System.out.println(goal);
    }