网格路径计数 2(Grid 2) 题解

思路分析

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

参考代码

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

const int MOD = 1000000007;
const int MAXF = 200005;

long long qpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int H, W, N;
    if (!(cin >> H >> W >> N)) return 0;
    vector<pair<int, int>> pts(N);
    for (int i = 0; i < N; ++i) cin >> pts[i].first >> pts[i].second;
    pts.push_back({H, W});
    sort(pts.begin(), pts.end());

    vector<long long> fact(MAXF, 1), inv(MAXF, 1);
    for (int i = 1; i < MAXF; ++i) fact[i] = fact[i - 1] * i % MOD;
    inv[MAXF - 1] = qpow(fact[MAXF - 1], MOD - 2);
    for (int i = MAXF - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;

    auto ways = [&](int dr, int dc) -> long long {
        if (dr < 0 || dc < 0) return 0;
        return fact[dr + dc] * inv[dr] % MOD * inv[dc] % MOD;
    };

    int m = (int)pts.size();
    vector<long long> dp(m, 0);
    for (int i = 0; i < m; ++i) {
        long long cur = ways(pts[i].first - 1, pts[i].second - 1);
        for (int j = 0; j < i; ++j) {
            if (pts[j].second <= pts[i].second) {
                cur = (cur - dp[j] * ways(pts[i].first - pts[j].first, pts[i].second - pts[j].second)) % MOD;
            }
        }
        if (cur < 0) cur += MOD;
        dp[i] = cur;
    }
    cout << dp[m - 1] << "\n";
    return 0;
}