1 条题解

  • 0
    @ 2026-11-12 21:58:24

    [Y] Grid 2(dp_y)题解

    题意简述

    H×WH\times W 网格(H,WH,W 达 2×1052\times10^5),K≤3000K \le 3000 个墙格。从 (1,1)(1,1) 只向右/下走到 (H,W)(H,W),求路径数  mod 109+7\bmod 10^9+7。

    思路

    网格太大,不能逐格 DP

    H×WH\times W 可达 4×10104\times10^{10},但墙只有 K≤3000K \le 3000 个。于是只对墙做容斥。

    无障碍的路径数

    从 (a,b)(a,b) 到 (c,d)(c,d)(c≥a,d≥bc \ge a, d \ge b)只向右/下走的路径数为

    ((c−a)+(d−b)c−a).\binom{(c-a)+(d-b)}{c-a}.

    预处理阶乘到 H+W≤4×105H+W \le 4\times10^5 即可 O(1)O(1) 计算。

    容斥 DP

    把墙按 (r,c)(r, c) 排序。设 fif_i = 从 (1,1)(1,1) 到第 ii 个墙格、且不经过任何更早的墙的方案数(即"合法到达该墙"的方案数):

    $$f_i = \binom{r_i+c_i-2}{r_i-1} - \sum_{j < i,\; r_j \le r_i,\; c_j \le c_i} f_j \cdot \binom{(r_i-r_j)+(c_i-c_j)}{r_i-r_j}.$$

    前半是"总共能到达的路径数",后半是"第一次碰到墙就撞在第 jj 个墙上的路径数"。相减即"不经过任何墙"。

    最后把终点当作一个额外的"墙",同样容斥:

    $$\text{ans} = \binom{H+W-2}{H-1} - \sum_{j} f_j \cdot \binom{(H-r_j)+(W-c_j)}{H-r_j}.$$

    复杂度

    时间 O(K2+H+W)O(K^2 + H + W),K=3000K=3000 时 9×1069\times10^6,可行;空间 O(H+W)O(H+W)。

    参考代码

    #include <cstdio>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long ll;
    const ll MOD = 1000000007LL;
    
    ll fac[400005], inv[400005];
    
    ll pw(ll b, ll e) { ll r = 1; b %= MOD; while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; } return r; }
    ll C(ll a, ll b) { if (a < 0 || b < 0 || a < b) return 0; return fac[a] * inv[b] % MOD * inv[a - b] % MOD; }
    
    int main() {
        int h, w, n;
        scanf("%d %d %d", &h, &w, &n);
        int mx = h + w;
        fac[0] = 1;
        for (int i = 1; i <= mx; i++) fac[i] = fac[i - 1] * i % MOD;
        inv[mx] = pw(fac[mx], MOD - 2);
        for (int i = mx; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
        vector<pair<int, int>> p(n);
        for (int i = 0; i < n; i++) scanf("%d %d", &p[i].first, &p[i].second);
        sort(p.begin(), p.end());
        vector<ll> f(n);
        for (int i = 0; i < n; i++) {
            ll v = C(p[i].first + p[i].second - 2, p[i].first - 1);
            for (int j = 0; j < i; j++)
                if (p[j].first <= p[i].first && p[j].second <= p[i].second)
                    v -= f[j] * C(p[i].first - p[j].first + p[i].second - p[j].second, p[i].first - p[j].first) % MOD;
            f[i] = ((v % MOD) + MOD) % MOD;
        }
        ll ans = C(h + w - 2, h - 1);
        for (int j = 0; j < n; j++)
            ans = (ans - f[j] * C(h - p[j].first + w - p[j].second, h - p[j].first)) % MOD;
        printf("%lld\n", ((ans % MOD) + MOD) % MOD);
        return 0;
    }
    

    易错点

    1. 阶乘要预处理到 H+WH+W(≤4×105\le 4\times10^5),不是 NN。
    2. 容斥时 v -= ... 会变负,最后要 (x % MOD + MOD) % MOD。
    3. 只统计 rj≤rir_j \le r_i 且 cj≤cic_j \le c_i 的前驱(否则不可能从 jj 走到 ii)。
    4. 排序后同一行/同一列的墙要正确处理(排序保证前面的 rj≤rir_j \le r_i,但仍要判断 cjc_j)。
    5. 起终点保证不是墙,所以不用特判。

    数据说明

    共 15 组:4 组官方样例(含 105×10510^5\times10^5、K=1K=1);2×22\times2/3×33\times3 的小规模墙;10×1010\times10、50×5050\times50、100×100100\times100 随机墙;H=W=2×105H=W=2\times10^5、K=3000K=3000 随机墙、首行墙、集中在小区域的墙、另一组随机墙。

    • 1

    信息

    ID
    34
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者