Submission #3267432

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <math.h>
#include <set>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

static const double PI = 3.1415926535897932384626433;
static const ll LL_MAX = (ll)1 << 62;
static const ll MOD = 1000000007;
///////////////////////////
////Prime Creator//////////
///////////////////////////
//bool Prime[100001] = {};
//void createPrime() {
//	ll n = 100001;
//	rep(i, 0, n) Prime[i] = true;
//	Prime[0] = false;
//	Prime[1] = false;
//	rep(i, 2, n) {
//		if (Prime[i]) {
//			rep(j, 2, n) {
//				if (j*i >= n)break;
//				Prime[j*i] = false;
//			}
//		}
//	}
//}
///////////////////////////
///////////////////////////

/////////////////////////
//Warshal Floyid/////////
/////////////////////////
//initialize
//
//static const ll LL_MAX = (ll)1 << 55;
//static const ll WF_MAX = 300;
//
//ll wf[WF_MAX][WF_MAX];
//void WarshalFloyid(int size) {
//	rep(k, 0, size)rep(i, 0, size)rep(j, 0, size)wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j]);
//}
//
////Bellmon ford
//// 隣接リストで使う辺を表す型
//struct Edge {
//	ll to, cost;  // 辺の接続先頂点, 辺の重み
//	Edge(ll to, ll cost) : to(to), cost(cost) {}  // コンストラクタ
//};
//typedef vector<vector<Edge> > AdjList;  // 隣接リストの型
//AdjList graph;  // グラフの辺を格納した構造体
//				// graph[v][i]は頂点vから出るi番目の辺Edge
//static const ll INF = (ll)1 << 55;
//vector<ll> dist; // 最短距離
//
//// 戻り値がtrueなら負の閉路を含む
//bool bellman_ford(int n, int s) { // nは頂点数、sは開始頂点
//	dist = vector<ll>(n, INF);
//	dist[s] = 0; // 開始点の距離は0
//	for (int i = 0; i < n; i++) {
//		for (int v = 0; v < n; v++) {
//			for (int k = 0; k < graph[v].size(); k++) {
//				Edge e = graph[v][k];
//				if (dist[v] != INF && dist[e.to] > dist[v] + e.cost) {
//					dist[e.to] = dist[v] + e.cost;
//					if (i == n - 1) {
//						return true;
//					}
//				}
//			}
//		}
//	}
//	return false;
//}

//RMQ Segment Tree
//const int MAX_N = 1 << 17;
//int n, dat[2 * MAX_N - 1];
//
//void init(int n_) {
//	n = 1;
//	while (n < n_) n *= 2;
//	rep(i, 0, 2 * n - 1) dat[i] = INT_MAX;
//}
//
//void update(int k, int a) {
//	k += n - 1;
//	dat[k] = a;
//	while (k > 0) {
//		k = (k - 1) / 2;
//		dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
//	}
//}
//
//int query(int a, int b, int k, int l, int r) {
//	if (r <= a || b <= l) return INT_MAX;
//
//	if (a <= l && r <= b)return dat[k];
//	else {
//		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
//		int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
//		return min(vl, vr);
//	}
//}
//
//int main() {
//	init(8);
//
//	update(0, 5);
//	update(1, 3);
//	update(2, 7);
//	update(3, 9);
//	update(4, 6);
//	update(5, 4);
//	update(6, 1);
//	update(7, 2);
//
//	cout << query(0, 6, 0, 0, n - 1) << endl;
//	return 0;
//}

//BIT Binary Index Tree
//int bit[MAX_N + 1], n;
//int sum(int i) {
//	int s = 0;
//	while (i > 0) {
//		s += bit[i];
//		i -= i;
//	}
//	return s;
//}
//void add(int i, int x) {
//	while (i <= n) {
//		bit[i] += x;
//		i += i & -i;
//	}
//}

//union find
//static const ll MAX_N = 200000;
//ll par[MAX_N];
//ll ran[MAX_N];
//
//void init(ll n) {
//	rep(i, 0, n) {
//		par[i] = i;
//		ran[i] = 0;
//	}
//}
//
//ll find(ll x) {
//	if (par[x] == x)  return x;
//	else return par[x] = find(par[x]);
//}
//
//void unite(ll x, ll y) {
//	x = find(x);
//	y = find(y);
//	if (x == y) return;
//
//	if (ran[x] < ran[y]) {
//		par[x] = y;
//	}
//	else {
//		par[y] = x;
//		if (ran[x] == ran[y]) ran[x]++;
//	}
//}
//bool same(ll x, ll y) {
//	return find(x) == find(y);
//}

//////////
//dijkstra
/////////
//ll N;
//static const ll MAX = 100001;
//static const ll INFTY = (ll)1 << 55;
//static const int WHITE = 1;
//static const int GRAY = 2;
//static const int BLACK = 3;
//vector<pair<int, int>>adj[MAX];
//ll d[MAX];
//ll pre[MAX];
//
//priority_queue<pair<int, int>>PQ;
//int color[MAX];
//ll n;
//void dijkstra(ll x) {
//	repe(i, 1, n) {
//		d[i] = INFTY;
//		color[i] = WHITE;
//	}
//
//	d[x] = 0;
//	PQ.push(make_pair(x, x));
//	color[x] = GRAY;
//	while (!PQ.empty()) {
//		pair<ll, ll> f = PQ.top(); PQ.pop();
//		ll u = f.second;
//		color[u] = BLACK;
//
//		if (d[u] < f.first * (-1))continue;
//
//		rep(j, 0, adj[u].size()) {
//			ll v = adj[u][j].first;
//			if (color[v] == BLACK)continue;
//			if (d[v] > d[u] + adj[u][j].second) {
//				d[v] = d[u] + adj[u][j].second;
//				pre[v] = u;
//				PQ.push(make_pair(d[v] * (-1), v));
//
//				color[v] = GRAY;
//			}
//		}
//	}
//}
//vector<ll> get_path(ll t) {
//	vector<ll> path;
//	for (; t != -1; t = pre[t])path.push_back(t);
//	reverse(path.begin(), path.end());
//	return path;
//}
//cin >> n;
//rep(i, 0, n - 1) {
//	ll a, b, c; cin >> a >> b >> c;
//	adj[a].push_back(make_pair(b, c));
//	adj[b].push_back(make_pair(a, c));
//}
//Topological Sort
//
//ll n, m, x, y, bit[20];
//ll dp[1 << 20];
//int main() {
//	cin >> n >> m; dp[0] = 1;
//	rep(i, 0, m) {
//		cin >> x >> y;
//		bit[y - 1] |= (1 << (x - 1));
//	}
//
//	rep(i, 1, 1 << n) {
//		rep(j, 0, n) {
//			if ((i & (i << j)) && (i | bit[j]) == i) {
//				dp[i] += dp[i - (i << j)];
//			}
//		}
//	}
//
//	return 0;
//}
//vector<int> L[101010];
//vector<int> T[101010];
//
//void createTree(int v, int p) {
//	for (int ne : L[v]) {
//		if (ne == p)continue;
//		T[v].push_back(ne);
//		createTree(ne, v);
//	}
//}
//
//ll dp[101010][2];
//int rec(int v, int color) {
//	if (dp[v][color] != -1)return dp[v][color];
//
//	int res = 1;
//	for (int ne : T[v]) {
//		if (color == 0) {
//			res *= rec(ne, 1);
//		}
//		else {
//			res *= rec(ne, 0) + rec(ne, 1);
//		}
//		res %= MOD;
//	}
//	return dp[v][color] = res;
//}
//
//int main() {
//	ll N; cin >> N;
//	rep(i, 0, N - 1) {
//		ll a, b; cin >> a >> b;
//		a--; b--;
//		L[a].push_back(b);
//		L[b].push_back(a);
//	}
//
//	createTree(0, -1);
//
//	rep(i, 0, 101010)rep(j, 0, 2)dp[i][j] = -1;
//	cout << (rec(0, 0) + rec(0, 1)) % MOD << endl;
//
//	return 0;
//}
//Combination
//ll POW(ll n, ll p) {
//	if (p == 0)return 1;
//	if (p == 1)return n;
//
//	ll t = POW(n, p / 2);
//	if (p & 1) return (t * t % MOD) * n % MOD;
//	else return t * t % MOD;
//}
//ll fact[1000001] = {};
//static const ll COMB_SIZE = 1000000;
//void factorial(ll f) {
//	fact[0] = fact[1] = 1;
//	rep(i, 1, COMB_SIZE) fact[i] = fact[i - 1] * i % MOD;
//}
//ll Combination(ll n, ll r) {
//	return ((fact[n] * (POW(fact[r], MOD - 2) % MOD)) % MOD * POW(fact[n - r], MOD - 2)) % MOD;
//}
//factorial(500000);
//
//static const ll MAX_N = 200000;
//ll par[MAX_N];
//ll ran[MAX_N];
//
//void init(ll n) {
//	rep(i, 0, n) {
//		par[i] = i;
//		ran[i] = 0;
//	}
//}
//
//ll find(ll x) {
//	if (par[x] == x)  return x;
//	else return par[x] = find(par[x]);
//}
//
//void unite(ll x, ll y) {
//	x = find(x);
//	y = find(y);
//	if (x == y) return;
//
//	if (ran[x] < ran[y]) {
//		par[x] = y;
//	}
//	else {
//		par[y] = x;
//		if (ran[x] == ran[y]) ran[x]++;
//	}
//}
//bool same(ll x, ll y) {
//	return find(x) == find(y);
//}
//
//ll A[200001] = {};
//ll B[200001] = {};
//ll S[200001] = {};
//int main() {
//	ll N; cin >> N;
//	rep(i, 0, N) {
//		ll a; cin >> a;
//		A[i] = a;;
//		S[i] = S[i - 1] + a;
//	}
//
//	ll minv = LL_MAX;
//	rep(k, 1, N - 1) {
//		ll m = S[k] / 2;
//		ll ub = k, lb = 0;
//		ll mid1;
//		rep(b, 0, 100) {
//			mid1 = (lb + ub) / 2;
//			if (S[mid1] - m > 0) {
//				ub = mid1;
//			}
//			else {
//				lb = mid1;
//			}
//		}
//		ll t = S[k] - S[mid1];
//		ll s = S[mid1];
//		//cout << "k " << k << " S[k] " << S[k] << " mid " << mid1 << " S[k] - S[mid - 1] " << t << " S[mid] " << s << endl;
//		cout << "k " << k << " S[k]: " << S[k] << " mid : " << mid1 << " t: " << t << " s: " << s << endl;
//
//		//debug
//		rep(i, 0, N) {
//			if (i <= k) B[i] = 0;
//			else  B[i] = S[i] - S[k];
//		}
//		//debug
//
//		m = B[N - 1] / 2;
//		ub = N, lb = k;
//		ll mid2;
//		rep(b, 0, 100) {
//			mid2 = (lb + ub) / 2;
//			if (B[mid2] - m > 0) {
//				ub = mid2;
//			}
//			else {
//				lb = mid2;
//			}
//		}
//		mid2++;
//		ll q = B[N - 1] - B[mid2];
//		ll r = B[mid2];
//		cout << "k " << k << " S[k]: " << S[k] << " mid2: " << mid2 << " q: " << q << " r: " << r << endl;
//
//		ll z = max(max(max(s, t), q), r) - min(min(min(s, t), q), r);
//		cout << "diff : " << z << endl;
//		minv = min(max(max(max(s, t), q), r) - min(min(min(s, t), q), r), minv);
//		cout << "minv : " << minv << endl;
//		cout << endl;
//	}
//	cout << minv << endl;
//
//	return 0;
//}

//union find
//static const ll MAX_N = 200000;
//ll par[MAX_N];
//ll ran[MAX_N];
//
//ll Z[100001] = {};
//void init(ll n) {
//	repe(i, 1, n) {
//		par[i] = i;
//		ran[i] = 0;
//		Z[i] = 1;
//	}
//}
//
//ll find(ll x) {
//	if (par[x] == x)  return x;
//	else return par[x] = find(par[x]);
//}
//void unite(ll x, ll y) {
//	x = find(x);
//	y = find(y);
//
//	if (x == y) return;
//
//	if (ran[x] < ran[y]) {
//		par[x] = y;
//		Z[y] += Z[x];
//		Z[x] = 0;
//	}
//	else {
//		par[y] = x;
//		Z[x] += Z[y];
//		Z[y] = 0;
//		if (ran[x] == ran[y]) ran[x]++;
//	}
//
//	////if (Z[x] < Z[y]) swap(x, y);
//	//Z[x] += Z[y];
//	//Z[y] = Z[x];
//}
//
//bool same(ll x, ll y) {
//	return find(x) == find(y);
//}
//
//static const ll MAX_N = 200000;
//ll par[MAX_N];
//ll ran[MAX_N];
//
//ll Z[100001] = {};
//void init(ll n) {
//	repe(i, 1, n) {
//		par[i] = i;
//		ran[i] = 0;
//		Z[i] = 1;
//	}
//}
//
//ll find(ll x) {
//	if (par[x] == x)  return x;
//	else return par[x] = find(par[x]);
//}
//void unite(ll x, ll y) {
//	x = find(x);
//	y = find(y);
//
//	if (x == y) return;
//
//	if (ran[x] < ran[y]) {
//		par[x] = y;
//		Z[y] += Z[x];
//		Z[x] = 0;
//	}
//	else {
//		par[y] = x;
//		Z[x] += Z[y];
//		Z[y] = 0;
//		if (ran[x] == ran[y]) ran[x]++;
//	}
//
//	////if (Z[x] < Z[y]) swap(x, y);
//	//Z[x] += Z[y];
//	//Z[y] = Z[x];
//}
//
//bool same(ll x, ll y) {
//	retur n find(x) == find(y);

//lca
//static const ll MAX_V = 1e5;
//static const ll MAX_LOG_V = 1e2;
//vector<ll> G[MAX_V];
//ll root;
//ll parent[MAX_LOG_V][MAX_V];
//ll depth[MAX_V];
//void dfs(ll v, ll p, ll d) {
//	parent[0][v] = p;
//	depth[v] = d;
//	rep(i, 0, G[v].size()) {
//		if (G[v][i] != p)dfs(G[v][i], v, d + 1);
//	}
//}
//void init(int V) {
//	dfs(root, -1, 0);
//	for (ll k = 0; k + 1 < MAX_LOG_V; k++) {
//		for (ll v = 1; v <= V; v++) {
//			if (parent[k][v] < 0) parent[k + 1][v] = -1;
//			else parent[k + 1][v] = parent[k][parent[k][v]];
//		}
//	}
//}
//
//ll lca(ll u, ll v) {
//	if (depth[u] > depth[v]) swap(u, v);
//	rep(k, 0, MAX_LOG_V) {
//		if ((depth[v] - depth[u]) >> k & 1) {
//			v = parent[k][v];
//		}
//	}
//	if (u == v)return u;
//	for (int k = MAX_LOG_V - 1; k >= 0; k--) {
//		if (parent[k][u] != parent[k][v]) {
//			u = parent[k][u];
//			v = parent[k][v];
//		}
//	}
//	return parent[0][u];
//}
//
//int main()
//{
//	ll n; cin >> n;
//	rep(i, 0, n - 1) {
//		ll x, y; cin >> x >> y;
//		G[x].push_back(y);
//		G[y].push_back(x);
//	}
//	root = 1;
//	init(n);
//
//	ll q; cin >> q;
//	rep(i, 0, q) {
//		ll a, b; cin >> a >> b;
//		ll L = lca(a, b);
//		cout << depth[a] + depth[b] - 2 * depth[L] + 1 << endl;
//	}
//	return 0;
//}
//
//char c[50][50] = {};
//int d[50][50] = {};
//void maze(ll R, ll C, ll sy, ll sx, ll gy, ll gx) {
//	sy--, sx--, gy--, gx--;
//	bool v[50][50] = {};
//	int x[4] = { 1,0,0,-1 };
//	int y[4] = { 0,1,-1,0 };
//
//	int ps = 0;
//	int pe = 0;
//	ll qx[10000] = {};
//	ll qy[10000] = {};
//
//	qy[pe] = sy;
//	qx[pe] = sx;
//	d[sy][sx] = 0;
//	v[sy][sx] = true;
//	pe++;
//
//	while (ps != pe) {
//		//pop
//		ll cy = qy[ps];
//		ll cx = qx[ps];
//		ps++;
//		if (cy == gy && cx == gx) {
//			break;
//		}
//
//		rep(i, 0, 4) {
//			//push
//			ll ny = cy + y[i];
//			ll nx = cx + x[i];
//
//			if (ny >= 0 && ny < R && nx >= 0 && nx < C && c[ny][nx] != '#' && !v[ny][nx]) {
//				qy[pe] = ny;
//				qx[pe] = nx;
//				pe++;
//				v[ny][nx] = true;
//				d[ny][nx] = d[cy][cx] + 1;
//			}
//		}
//	}
//}
//
//digit DP
//ll mod = 1e9 + 7;
//ll dp[20][2];
//
//int main() {
//	string A; cin >> A;
//	ll n = A.length();
//	//dp
//	dp[0][0] = 1;
//
//	rep(i, 0, n) {//桁数
//		rep(j, 0, 2) {//0 or 1
//			//0 なら その桁の数まで、1なら９まで全部
//			ll lim = j ? 9 : A[i] - '0';
//			rep(d, 0, lim + 1) {
//				(dp[i + 1][j || d < lim] += dp[i][j]);
//			}
//		}
//	}
//
//	ll ans = 0;
//	rep(j, 0, 2) (ans += dp[n][j]);
//	cout << ans << endl;
//
//	return 0;
//}

ll n, d, x, y;
double nCk[1001][1001];

double solve() {
	if (x % d != 0 || y % d != 0)return 0;
	if (x / d > n || y / d > n)return 0;
	x = abs(x) / d; y = abs(y) / d;
	if ((x + y) % 2 != n % 2) return 0;
	double res = 0;

	rep(k, 0, n + 1) {
		if (k % 2 != x % 2)continue;
		ll lr = (k + x) / 2, ud = (n - k + y) / 2;
		if (lr > k || ud > n - k)continue;
		res += nCk[n][k] * nCk[k][lr] * nCk[n - k][ud];
	}
	return res;
}

int main() {
	nCk[0][0] = 1;

	rep(i, 0, 1000)rep(j, 0, 1000) {
		nCk[i + 1][j] += nCk[i][j] / 2;
		nCk[i + 1][j + 1] += nCk[i][j] / 2;
	}
	cin >> n >> d >> x >> y;
	printf("%.10f\n", solve());
	return 0;
}

Submission Info

Judge Result