Submission #188219

---

Source Code Expand

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <queue>
#include <sstream>
#include <utility>
#include <vector>

using namespace std;

typedef long long Long;
#define whole(xs) xs.begin(), xs.end()

int N, D;
int X, Y;
void input() {
    cin >> N >> D;
    cin >> X >> Y;
}

const int dy[] = {1, 0, -1, 0},
          dx[] = {0, 1, 0, -1};
double dfs(int n, int y, int x) {
    if (n == N) {
        return y == Y && x == X;
    }
    double R = 0;
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i],
            nx = x + dx[i];
        R += dfs(n + 1, ny, nx);
    }
    return R / 4.0;
}

void solve() {
    if (not (abs(X) % D == 0 && abs(Y) % D == 0)) {
        printf("%.10f\n", 0.);
        return;
    }
    X = X / D;
    Y = Y / D;
    if (X > N || Y > N) {
        printf("%.10f\n", 0.);
        return;
    }
    if ((N - (X + Y)) % 2 != 0) {
        printf("%.10f\n", 0.);
        return;
    }
    //cerr << N << " " << X << " " << Y << endl;
    double Ans = 1;
    for (int i = N; i > 0; i--) {
        Ans *= (double(i) / 4.0);
    }
    int R = N - (X + Y);
    //cerr << Ans << endl;
    double Q = 0.0;
    for (int x1 = 0; x1 * 2 <= R; x1++) {
        int y1 = R / 2 - x1;
        double S = 1.0;
        for (int i = 1; i <= X + x1; i++) {
            S /= i;
        }
        for (int i = 1; i <= Y + y1; i++) {
            S /= i;
        }
        for (int i = 1; i <= x1; i++) {
            S /= i;
        }
        for (int i = 1; i <= y1; i++) {
            S /= i;
        }
        Q += S;
    }
    printf("%.10f\n", Ans * Q);
}

int main() {
    input(); solve();
    return 0;
}

Submission Info

Judge Result