Submission #188074

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define gc getchar
int getint() { unsigned int c; int x = 0; while (((c = gc()) - '0') >= 10) { if (c == '-') return -getint(); if (!~c) exit(0); } do { x = (x << 3) + (x << 1) + (c - '0'); } while (((c = gc()) - '0') < 10); return x; }
int getstr(char *s) { int c, n = 0; while ((c = gc()) <= ' ') { if (!~c) exit(0); } do { s[n++] = c; } while ((c = gc()) > ' ' ); s[n] = 0; return n; }
template<class T> inline bool chmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<class T> inline bool chmax(T &a, T b) { return a < b ? a = b, 1 : 0; }

typedef long double R;
static const R minf = -1e100;
static const R meps = 1e-30;
struct L {
    R v;
    L() : v(minf) {} L(R x) { v = (x > meps) ? v = log(x) : minf; }
    L(const L& x) { v = max(minf, x.v); }
    R to_real() const { return exp(v); }
};
const L LONE = L(1), LZERO = L(0);
L operator*(L x, L y) { x.v += y.v; return x; } L& operator*=(L& x, L y) { return x = x * y; }
L operator/(L x, L y) { x.v -= y.v; return x; } L& operator/=(L& x, L y) { return x = x / y; }
L operator+(L x, L y) { if (y.v > x.v) swap(x, y); if (x.v - y.v > 45) return x; x.v += log1p(exp(y.v - x.v)); return x; }
L& operator+=(L& x, L y) { return x = x + y; }
const int MAXN = 2000;
L fact[MAXN];
void make_fact(int n) { fact[0] = LONE; for (int i = 1; i <= n; i++) fact[i] = L((R)i) * fact[i - 1]; }
L comb(int n, int k) { if (k < 0 or n < k) return LZERO; return fact[n] * fact[n - k] / fact[k]; }
ostream& operator<<(ostream& os, L x) { os << x.v; return os; }


//
int main () {
    int i, j, tcc, tc = 1 << 28;

    make_fact(1111);

    for (tcc = 0; tcc < tc; tcc++) {
        int N = getint();
        int D = getint();
        int X = getint(), Y = getint();
        if (X < 0) X = -X;
        if (Y < 0) Y = -Y;

        int xneed = X / D;
        int yneed = Y / D;
        int rest = N - xneed - yneed;

        if (X % D or Y % D or rest & 1 or xneed + yneed > N) { puts("0.0"); return 0; }

        vector<L> res;
        for (int xs = 0; xs <= rest; xs += 2) {
            int ys = rest - xs;
            int xs1 = xneed + xs / 2;
            int xs2 = xs / 2;
            int ys1 = yneed + ys / 2;
            int ys2 = ys / 2;
            res.push_back(fact[N] / fact[xs1] / fact[xs2] / fact[ys1] / fact[ys2]);
        }
        L four = 1;
        for (i = 0; i < N; i++) four = four * 4;
        for (i = 0; i < res.size(); i++) res[i] = res[i] / four;

        R fin = 0;
        for (i = 0; i < res.size(); i++) fin += res[i].to_real();

        cout.precision(14);
        cout << fin << endl;
    }
    return 0;
}

Submission Info

Judge Result