abc 265 E

一道比较典的 DP 题，有三种走法，问走 n 步有几种走法（有一些点不能走）
用 map 存有障碍的点
由 i, j, k 映射到坐标，如果当前节点不为障碍点，则从之前的点继承状态

#include <bits/stdc++.h>

using namespace std;

const int N = 303, mod = 998244353;

int dp[N][N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    long long a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;

    map<array<long long, 2>, bool> Map; 

    for (int i = 0; i < m; i ++) {
        int x, y;
        cin >> x >> y;
        Map[{x, y}] = true;
    }

    int ans = 0;

    for (int i = 0; i <= n; i ++) {
        for (int j = 0; j + i <= n; j ++) {
            for (int k = 0; k + i + j <= n; k ++) {
                if (i == j && j == k && k == 0) {
                    dp[i][j][k] = 1;
                } else if (!Map[{a * i + c * j + e * k, b * i + d * j + f * k}]) {
                    if (i) dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k]) % mod;
                    if (j) dp[i][j][k] = (dp[i][j][k] + dp[i][j - 1][k]) % mod;
                    if (k) dp[i][j][k] = (dp[i][j][k] + dp[i][j][k - 1]) % mod;
                }

                if (i + j + k == n) {
                    ans = (ans + dp[i][j][k]) % mod;
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}