fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define f first
  4. #define s second
  5.  
  6. using namespace std;
  7.  
  8. const int N=1510,mod=1e9+7; //N should be set to maxN+D
  9. int add(int a,int b){
  10. 	a+=b;
  11. 	if(a>=mod)
  12. 		a-=mod;
  13. 	return a;
  14. }
  15. vector<int> pwr(1,1),dx={1,-1,0,0},dy={0,0,1,-1};
  16. int dp[2][N][N],d;
  17. int get(int x,int y,int n){
  18. 	if(x==-1)
  19. 		x=1;
  20. 	if(y==-1)
  21. 		y=1;
  22. 	if(x<y)
  23. 		swap(x,y);
  24. 	if(x+y<=d)
  25. 		return 0;
  26. 	if(x+y-n>d)
  27. 		return pwr[n];
  28. 	return dp[n&1][x][y];
  29. }
  30. pair<int,int> points[N*N];
  31. int last=0,nxt;
  32. int main()
  33. {
  34. 	int x,y,n;
  35. 	scanf("%i %i %i %i",&x,&y,&n,&d);
  36. 	x=abs(x);
  37. 	y=abs(y);
  38. 	if(x<y)
  39.         swap(x,y);
  40. 	for(int i=1;i<N;i++)
  41. 		pwr.push_back((long long)pwr.back()*4%mod);
  42. 	for(int x=d+1;x>=0;x--)
  43. 		for(int y=x;y>=0;y--)
  44. 			if(x+y==d+1)
  45.                 points[nxt++]={x,y};
  46. 	for(int i=1;i<=n;i++){
  47. 		for(int j=0;j<nxt;j++){
  48.             dp[i&1][points[j].f][points[j].s]=0;
  49.             int d=abs(x-points[j].f)+abs(y-points[j].s);
  50.             if(d>n-i)
  51.                 continue;
  52. 			for(int k=0;k<4;k++)
  53. 				dp[i&1][points[j].f][points[j].s]=add(dp[i&1][points[j].f][points[j].s],get(points[j].f+dx[k],points[j].s+dy[k],i-1));
  54. 		}
  55. 		if(i!=n){
  56.             int limit=nxt;
  57.             for(int j=last;j<limit;j++)
  58.                 points[nxt++]={points[j].f+1,points[j].s};
  59.             if(points[limit-1].f!=points[limit-1].s)
  60.                 points[nxt++]={points[limit-1].f,points[limit-1].s+1};
  61. 			last=limit;
  62. 		}
  63. 	}
  64. 	printf("%i\n",get(x,y,n));
  65. 	return 0;
  66. }
  67.  
Success #stdin #stdout 4.08s 23992KB
comments (?)
stdin
copy 
198 531 1500 4
stdout
copy 
375005153
https://ideone.com/kprHLL
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!