fork download
  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] = 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 = 1; 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. // (x, y) chính là toạ độ hiện tại mà ta đang ở
  45. ll x = a * n1 + c * n2 + e * n3, y = b * n1 + d * n2 + f * n3;
  46. int& cur = dp[i][n1][n2];
  47. cur = 0;
  48. if (obstacles.count({x, y})) continue;
  49. // Bước thứ i
  50. // Đi bước loại 1
  51. if (n1 > 0) add(cur, dp[i - 1][n1 - 1][n2]);
  52. // Đi bước loại 2
  53. if (n2 > 0) add(cur, dp[i - 1][n1][n2 - 1]);
  54. // Đi bước loại 3
  55. if (n3 > 0) add(cur, dp[i - 1][n1][n2]);
  56. }
  57. }
  58. }
  59.  
  60. int ans = 0;
  61. for (int n1 = 0; n1 <= n; n1++) {
  62. for (int n2 = 0; n1 + n2 <= n; n2++) {
  63. add(ans, dp[n][n1][n2]);
  64. }
  65. }
  66.  
  67. cout << ans << '\n';
  68. }
Success #stdin #stdout 0.01s 5500KB
stdin
2 2
1 1 1 2 1 3
1 2
2 2
stdout
5