fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<ll, ll> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int MOD = 998244353; 
  12. const int N = 3e2 + 5; 
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD; 
  17. }
  18.  
  19. int n, m;   
  20. ll a, b, c, d, e, f; 
  21. map<ii, bool> obstacles; 
  22.  
  23. int dp[N][N][N]; // dp[i][n1][n2] = Tổng số đường đi gồm i bước, trong đó đã đi n1 bước loại 1 và n2 bước loại 2
  24. 				 // Ta có n1 + n2 + n3 = i 
  25. 				 //  =>             n3 = i - n1 - n2
  26.  
  27. int main() {
  28. 	ios::sync_with_stdio(false); 
  29. 	cin.tie(nullptr); 	
  30. 	cin >> n >> m; 
  31. 	cin >> a >> b >> c >> d >> e >> f; 
  32.  
  33. 	for (int i = 0; i < m; i++) {
  34. 		ll x, y; 
  35. 		cin >> x >> y; 
  36. 		obstacles[{x, y}] = true; 
  37. 	}
  38.  
  39. 	dp[0][0][0] = 1;   
  40. 	for (int i = 0; i < n; i++) {
  41. 		for (int n1 = 0; n1 <= i; n1++) {
  42. 			for (int n2 = 0; n1 + n2 <= i; n2++) {
  43. 				int n3 = i - n1 - n2;   
  44. 				ll cur_x = a * n1 + c * n2 + e * n3, cur_y = b * n1 + d * n2 + f * n3; 
  45. 				// Bước thứ i + 1
  46. 				// Đi 1 bước loại 1 
  47. 				if (!obstacles.count({cur_x + a, cur_y + b})) {
  48. 					add(dp[i + 1][n1 + 1][n2], dp[i][n1][n2]);  
  49. 				}
  50. 				// Đi 1 bước loại 2
  51. 				if (!obstacles.count({cur_x + c, cur_y + d})) {
  52. 					add(dp[i + 1][n1][n2 + 1], dp[i][n1][n2]); 
  53. 				}
  54. 				// Đi 1 bước loại 3
  55. 				if (!obstacles.count({cur_x + e, cur_y + f})) {
  56. 					add(dp[i + 1][n1][n2], dp[i][n1][n2]);
  57. 				}
  58. 			}
  59. 		}
  60. 	}
  61.  
  62. 	int ans = 0;  
  63. 	for (int n1 = 0; n1 <= n; n1++) {
  64. 		for (int n2 = 0; n1 + n2 <= n; n2++) {
  65. 			add(ans, dp[n][n1][n2]); 
  66. 		}
  67. 	}
  68.  
  69. 	cout << ans << '\n';
  70. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
2 2
1 1 1 2 1 3
1 2
2 2
stdout
copy 
5
https://ideone.com/TwfvVV
language:
C++14 (gcc 8.3)
created:
1 year 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!