縦と横を独立に解くことと,全探索する部分を決める方針.
問題を簡単にする
(i) d = 1 に帰着
(x,y がともに d の倍数)でなければ不可能.(x,yがともに dの倍数)のとき,x,y を d で割ることで d = 1と仮定してよい.
今回は関係ないが,最大公約数で割って,最大公約数が 1 の場合に帰着するというテクニックもある.
(ii) 縦と横を独立に解く
(iii) 全探索できる部分はしてしまう
横に移動する回数 i を全探索する.縦に移動する回数は n - i と一意に決まる.
(0) 横移動について考える.右に a 回, 左に b 回移動したとすると,
を得る.よって,a,b が存在すれば一意に定まる.このときの確率はとなる.
(1) 縦も同様.
(2) n 個の移動のうち,i 回横移動が選ばれる確率は,.
これら(0),(1),(2) は独立.
前処理として, を double 型で求めておけばよい.パスカルの三角形を使うと楽.階乗の計算をするのは,分子と分母が大きすぎて正しく求まらない.
typedef long long ll;
#define srep(i,s,t) for (ll i = (s); i < (t); ++i)
#define rep(i,n) srep(i,0,(n))
template<typename T> bool in(T x, T l, T r){
if(l >= r) return false;
return l <= x && x < r;
}
template<typename T> bool in(T x, T a){ return in(x, (T)0, a); }
int main() {
ll n, m, k, q, d;
cin >> n >> d;
ll x, y ; cin >> x >> y;
if(x < 0) x *= -1;
if(y < 0) y *= -1;
bool f = true;
if(x % d == 0) x /= d;
else f = false;
if(y % d == 0) y /= d;
else f = false;
d = 1;
if(!f) {
cout << 0 << endl;
return 0;
}
pas[0][0] = 1;
rep(i,n+1) {
pas[i+1][0] = pas[i][0]/(double)2;
rep(r,i+1){
pas[i+1][r+1] = (pas[i][r] + pas[i][r+1])/2;
}
// pas[i+1][i+1] = pas[i][i]/(double)2;
}
auto func = [&](ll i, ll x) -> double {
ll a,b;
ll s = x + i;
ll t = -x + i;
if(s % 2 == 0) a = s/2; else return 0;
if(t % 2 == 0) b = s/2; else return 0;
if(!in(a,i+1)) return 0;
if(!in(b,i+1)) return 0;
return pas[i][a];
};
double ans = 0;
rep(i,n+1){
ans += pas[n][i] *func(i,x) * func(n-i,y);
}
printf("%.10lf\n",ans);
return 0;
}