Submission #1179785

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define int long long


const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};

int N,D,X,Y,r;

int memo[100][100][100];
double dfs(int count,int nowX,int nowY){
  double ret=0.0;

  if(memo[count][nowX][nowY]>0)return memo[count][nowX][nowY];

  if(count==N&& nowX==X && nowY==Y)return 1.0;
  else if(count==N)return 0.0;


  for(int i=0;i<4;i++){
    ret+=dfs(count+1,nowX+dx[i],nowY+dy[i]);
  }

  memo[count][nowX][nowY]=ret;

  return memo[count][nowX][nowY];

}

int pow(int x,int y){
  if(y==0)return 1;
  if(y==1)return x;
  int res=1;
  while(y){
      if(y&1)res*=x;
      x=x*x;
      y>>=1;
  }
  return res;
}
signed main(){
  //N<=30 で解いてみる

  cin>>N>>D>>X>>Y;
  if(X%D!=0 || Y%D!=0){
    cout<<0.0<<endl;
    return 0;
  }
  X/=D;Y/=D;

  //配列が負になるので+50
  X+=N;Y+=N;

  cout<<dfs(0,N,N)/pow(4,N)<<endl;



  return 0;
}

Submission Info

Judge Result