k 维空间路径问题(K-Dimensional Lattice Paths) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const long long MOD = 998244353LL;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k, n;
    if (!(cin >> k >> n)) return 0;
    vector<vector<int>> pts(n + 1, vector<int>(k));
    int max_sum = 0;
    for (int d = 0; d < k; ++d) {
        cin >> pts[n][d];
        max_sum += pts[n][d];
    }
    for (int i = 0; i < n; ++i) {
        for (int d = 0; d < k; ++d) {
            cin >> pts[i][d];
        }
    }
    sort(pts.begin(), pts.begin() + n);
    vector<long long> fact(max_sum + 1, 1), invFact(max_sum + 1, 1);
    for (int i = 1; i <= max_sum; ++i) fact[i] = (fact[i - 1] * i) % MOD;
    invFact[max_sum] = power(fact[max_sum], MOD - 2);
    for (int i = max_sum - 1; i >= 0; --i) invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;

    auto ways = [&](const vector<int>& A, const vector<int>& B) -> long long {
        int sum = 0;
        long long den = 1;
        for (int d = 0; d < k; ++d) {
            int diff = B[d] - A[d];
            if (diff < 0) return 0LL;
            sum += diff;
            den = (den * invFact[diff]) % MOD;
        }
        return (fact[sum] * den) % MOD;
    };

    vector<int> origin(k, 0);
    vector<long long> dp(n + 1, 0);
    for (int i = 0; i <= n; ++i) {
        long long val = ways(origin, pts[i]);
        for (int j = 0; j < i; ++j) {
            bool le = true;
            for (int d = 0; d < k; ++d) {
                if (pts[j][d] > pts[i][d]) {
                    le = false;
                    break;
                }
            }
            if (le) {
                val = (val - dp[j] * ways(pts[j], pts[i])) % MOD;
            }
        }
        if (val < 0) val += MOD;
        dp[i] = val;
    }
    cout << dp[n] << "\n";
    return 0;
}