ABC 11 D - 大ジャンプ ( Probability )

D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder
Problem Statement: Given n: number of jumps, d: distance of each jump, find the probability to land in coordinate ( x, y ) when n jumps are made arbitrarily.
We will first get rid of d by dividing it from both x and y. If any of them will have remainder, the probability to land on ( x, y ) will be 0%. Then consider the symmetrical property of the plane, we can suppose x = abs( x ) and y = abs( y ) without losing generality. After precomputing P( n, m ): Probability of taking m elements from n distinct elements, we will find that if we split the problem into 2 different vectors, vertical and horizontal, when the number of jumps in one vector is fixed, the other will be fixed as well. We can enumerate the number of jumps in one vector, and calculate the probability to land on ( x, y ) in each case, and in the end we will sum them up. Note that when the number of jumps in one vector is determined, there will either be no way to reach the goal, or have a unique distribution of moves for both opposite directions i.e. 200 steps and wish to move to 50, one of the directions will have to move ( 200 + 50 ) / 2 = 125 steps.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;
const int MAXD = 1e9 + 9;
const int MAXABXY = 1e9 + 9;
 
int n, d;
int gx, gy;
 
double p[ MAXN ][ MAXN ];
 
void preP(){
    p[ 0 ][ 0 ] = 1.0;
    for(int i = 1; i < MAXN; ++i)
        for(int j = 0; j <= i; ++j)
            p[ i ][ j ] = ( p[ i - 1 ][ j - 1 ] + p[ i - 1 ][ j ] ) / 2.0;
}
 
void solve(){
    gx = abs( gx ), gy = abs( gy );
    if( gx % d || gy % d ){
        puts("0");
        return;
    }
    gx /= d, gy /= d;
    preP();
    double ans = 0.0;
    for(int i = gx; n - i >= gy; ++i) // i: number of jumps in x vector
        if( ( i + gx >> 1 ) - ( i - ( i + gx >> 1 ) ) == gx ) // if it is possible to jump to x
            if( ( n - i + gy >> 1 ) - ( n - i - ( n - i + gy >> 1 ) ) == gy ) // if possible to jump to y
                ans += p[ n ][ i ] * p[ i ][ i + gx >> 1 ] * p[ n - i ][ n - i + gy >> 1 ];
    printf("%.10lf\n", ans);
}
 
int main(){
    scanf("%d%d%d%d", &n, &d, &gx, &gy);
    solve();
    return 0;
}