fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long mod = 1000000007LL;
  5.  
  6. long long power(long long a, long long b)
  7. {
  8. 	long long ret = 1;
  9. 	while(b)
  10. 	{
  11. 		if(b&1)
  12. 			ret = (ret * a) % mod;
  13. 		a = (a * a) % mod;
  14. 		b /= 2;
  15. 	}
  16. 	return (ret + mod) % mod;
  17. }
  18.  
  19. long long inv(long long x)
  20. {
  21. 	return power(x, mod - 2);
  22. }
  23.  
  24. int maxstep = 200;
  25. long long grid[401][401];
  26. long long nextGrid[401][401];
  27. long long value[401][401];
  28. long long ans[401];
  29. int dx[] = {1, -1, 0, 0};
  30. int dy[] = {0, 0, 1, -1};
  31.  
  32. class RandomWalkOnGrid
  33. {
  34. 	public:	int getExpectation(int x0, int y0, int t, int n, int m)
  35. 	{
  36. 		for(int i = -maxstep; i <= maxstep; i++)
  37. 			for(int j = -maxstep; j <= maxstep; j++)
  38. 			{
  39. 				value[i+maxstep][j+maxstep] = (power(x0 + i, n) * power(y0 + j, m)) % mod;
  40. 			}
  41. 		memset(grid, 0, sizeof(grid));
  42. 		memset(ans, 0, sizeof(ans));
  43. 		grid[maxstep][maxstep] = 1;
  44. 		for(int c = 0; c <= maxstep; c++)
  45. 		{
  46.  
  47. 			memset(nextGrid, 0, sizeof(nextGrid));
  48. 			for(int i = 0; i <= 2*maxstep; i++)
  49. 				for(int j = 0; j <= 2*maxstep; j++)
  50. 					ans[c] = (ans[c] + value[i][j] * grid[i][j]) % mod;
  51.  
  52. 			if(c < maxstep)
  53. 			{
  54. 				for(int i = 0; i <= 2*maxstep; i++)
  55. 					for(int j = 0; j <= 2*maxstep; j++)
  56. 						if(grid[i][j] > 0)
  57. 							for(int dir = 0; dir < 4; dir ++)
  58. 								nextGrid[i+dx[dir]][j+dy[dir]] = (nextGrid[i+dx[dir]][j+dy[dir]] + grid[i][j]) % mod;
  59.  
  60. 				for(int i = 0; i <= 2*maxstep; i++)
  61. 					for(int j = 0; j <= 2*maxstep; j++)
  62. 						grid[i][j] = nextGrid[i][j];
  63. 			}
  64. 			ans[c] *= inv(power(4, c));
  65. 			ans[c] %= mod;
  66. 		}
  67. 		if(t <= maxstep)
  68. 			return (ans[t] * power(4, t)) % mod;
  69. 		else
  70. 		{
  71. 			long long ret = 0;
  72. 			for(int i = 0; i <= maxstep; i++)
  73. 			{
  74. 				long long cur = ans[i];
  75. 				for(int j = 0; j <= maxstep; j++)
  76. 					if(j != i)
  77. 					{
  78. 						cur *= (t - j + mod) % mod;
  79. 						cur %= mod;
  80. 						cur *= inv((i - j + mod) % mod);
  81. 						cur %= mod;
  82. 					}
  83. 				ret += cur;
  84. 				ret %= mod;
  85. 			}
  86. 			return (ret * power(4, t)) % mod;
  87. 		}
  88. 		return -1;
  89. 	}
  90. };
  91.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/z1GXl8
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!