登山

GitHub跳转原题关系图返回列表

路径受 y≤x 的山脊界限约束,用反射原理 O(1) 求两点间受限路径数,再按首次踩到的坑做容斥 DP,复杂度 O(N+C^2)。

OJ: roj

题目 ID: 1810

难度:普及+/提高-

标签:数学组合数学容斥反射原理

创建: 2026-10-08 04:53

更新: 2026-10-08 04:53

形式化题目

给出整数 NN 和障碍点集合 SS(∣S∣=C|S| = C,每个点 (x,y)(x,y) 满足 x⩾yx \geqslant y,(0,0),(N,N)∉S(0,0),(N,N) \notin S)。 在格点上从 (0,0)(0,0) 出发,每步只能走 (x+1,y)(x+1,y) 或 (x,y+1)(x,y+1), 且站在 (x,x)(x,x) 上时不允许走 (x,y+1)(x,y+1),求到达 (N,N)(N,N) 且不经过 SS 中任何点的路径数, 答案对 109+710^9+7 取模。

"在 (x,x)(x,x) 上不能向上走"这一条等价于

x⩾y对路径上的每一个点都成立,x \geqslant y \quad \text{对路径上的每一个点都成立},

即路径全程不越过直线 y=xy = x。下面把这种路径称为合法路径。

正解

思路

NN 可以到 10510^5,直接在 N×NN \times N 的格子上做二维 DP 是 O(N2)=1010O(N^2) = 10^{10}, 必然超时超内存;而 CC 只有 10001000,所以把障碍点当作状态,用组合数在它们之间跳。

第一步:两点间的受限路径数。 先不管障碍,只要求从 A(sx,sy)A(sx,sy) 走到 B(tx,ty)B(tx,ty) 且不越过 y=xy=x。 记 dx=tx−sx, dy=ty−sydx = tx-sx,\ dy = ty-sy。无界限约束时有 (dx+dydx)\binom{dx+dy}{dx} 条路径。 越过界限的路径必然经过直线 y=x+1y = x+1,把这些路径从第一次碰到 y=x+1y=x+1 的位置起 关于该直线镜像翻转,就与"从 AA 关于 y=x+1y=x+1 的对称点 A′(sy−1, sx+1)A'(sy-1,\ sx+1) 出发走到 BB" 的路径一一对应。A′A' 到 BB 的步数是 dx+dydx+dy,向右步数是 tx−(sy−1)=ty−sx−1tx-(sy-1) = ty-sx-1,于是

path⁡(A→B)=(dx+dydx)−(dx+dyty−sx−1).\operatorname{path}(A \to B) = \binom{dx+dy}{dx} - \binom{dx+dy}{ty-sx-1}.

当 ty⩽sxty \leqslant sx 时下标 ty−sx−1<0ty-sx-1 < 0,反射项按 00 处理(此时根本不可能碰到 y=x+1y=x+1)。

第二步:按"首次踩到的坑"容斥。 把所有坑按 (x,y)(x,y) 升序排成 P1,…,PmP_1, \dots, P_m (同一横坐标时纵坐标小的在前)。这样若 PjP_j 能成为 PiP_i 路径上的中间点,必有 j<ij < i,DP 无环。 定义

f[i]=从 (0,0) 走到 Pi, 途中不踩任何坑的合法路径数.f[i] = \text{从 } (0,0) \text{ 走到 } P_i,\ \text{途中不踩任何坑的合法路径数}.

无视其他坑先算出 path⁡((0,0)→Pi)\operatorname{path}((0,0)\to P_i),再减去"第一个踩到的坑是某个 PjP_j"的路径: 前缀由 f[j]f[j] 负责保证不踩坑,后缀从 PjP_j 到 PiP_i 只要保持合法(可以自由踩其他坑)。于是

f[i]=path⁡((0,0)→Pi)−∑j<i, yj⩽yif[j]⋅path⁡(Pj→Pi).f[i] = \operatorname{path}((0,0) \to P_i) - \sum_{j < i,\ y_j \leqslant y_i} f[j] \cdot \operatorname{path}(P_j \to P_i).

(只需检查 yj⩽yiy_j \leqslant y_i:由于已按 xx 排序,j<ij<i 时 xj⩽xix_j \leqslant x_i, 若 yj>yiy_j > y_i 则 PjP_j 在 PiP_i 右上方,不可能被经过;反之 path⁡\operatorname{path} 自身会返回 00。)

最后把整个终点也看成"第 m+1m+1 个点",答案就是

Ans=path⁡((0,0)→(N,N))−∑i=1mf[i]⋅path⁡(Pi→(N,N)).\text{Ans} = \operatorname{path}((0,0) \to (N,N)) - \sum_{i=1}^{m} f[i] \cdot \operatorname{path}(P_i \to (N,N)).

每一步都只用到  mod 109+7\bmod 10^9+7 下的乘法与减法,预处理 0∼2N0 \sim 2N 的阶乘及阶乘逆元 即可让任意组合数 O(1)O(1) 得出。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 04:53
# update_at: 2026-10-08 04:53

import sys
from itertools import accumulate

MOD = 10 ** 9 + 7        # 答案取模的模数

type Point = tuple[int, int]   # 山上的一个坑 (x, y)

FAC: list[int] = []      # FAC[i] = i! mod MOD,由 build_tables 按 2N 上界填充
INVFAC: list[int] = []   # INVFAC[i] = (i!)^(-1) mod MOD


def build_tables(limit: int) -> None:
    """填充阶乘表与阶乘逆元表:任意组合数 C(n, k) 之后可以 O(1) 算出。"""
    global FAC, INVFAC
    FAC = [1, *accumulate(range(1, limit + 1), lambda a, b: a * b % MOD)]
    # 从 inv(limit!) 出发逐个乘回 i,第 k 项是 inv((limit-k)!);倒置后就是升序的
    # INVFAC[i] = inv(i!)(i = 0..limit)
    INVFAC = [*accumulate(range(limit, 0, -1), lambda a, b: a * b % MOD,
                          initial=pow(FAC[limit], MOD - 2, MOD))][::-1]


def paths(sx: int, sy: int, tx: int, ty: int) -> int:
    """从 (sx,sy) 走到 (tx,ty) 且全程不越过直线 y=x 的路径数(反射原理,O(1))。"""
    if tx < sx or ty < sy:
        return 0                                     # 终点落在起点左下方,根本走不到
    total = tx - sx + ty - sy                        # 总步数 dx + dy
    all_ways = FAC[total] * INVFAC[tx - sx] % MOD * INVFAC[ty - sy] % MOD
    reflect_pick = ty - sx - 1                       # 越过 y=x+1 的路径数即 C(total, ty-sx-1)
    if reflect_pick < 0:
        return all_ways                              # 起点已经在高处,不可能碰到 y=x+1
    bad_ways = FAC[total] * INVFAC[reflect_pick] % MOD * INVFAC[total - reflect_pick] % MOD
    return (all_ways - bad_ways) % MOD


def count_paths(n: int, holes: list[Point]) -> int:
    """容斥:返回 (0,0)->(n,n)、全程不越过 y=x 且不踩任何坑的路径数。

    holes 已按 (x, y) 升序去重;把踩了坑的路径按"踩到的第一个坑"分类,前缀由 first[j]
    保证不踩坑、后缀从 j 走到 i 只需保持合法,两者相乘即该类路径数。
    """
    first: list[int] = []       # first[i] = 走到 holes[i] 且它是首个被踩到的坑的方案数
    for xi, yi in holes:
        ways = paths(0, 0, xi, yi)                     # 先算无视其他坑的方案数
        for (xj, yj), fj in zip(holes, first):         # zip 到 first 结束,即只枚举更早的坑
            if yj <= yi:                               # 否则坑 j 不可能出现在通往坑 i 的路上
                ways -= fj * paths(xj, yj, xi, yi)     # 扣除"首个坑是 j、随后走到 i"的方案
        first.append(ways % MOD)

    ans = paths(0, 0, n, n) - sum(
        f * paths(x, y, n, n) for (x, y), f in zip(holes, first)   # 末尾踩过坑的路径按首坑扣除
    )
    return ans % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, c = next(data), next(data)
    pts: list[Point] = [(next(data), next(data)) for _ in range(c)]   # 每个坑的坐标

    build_tables(2 * n + 1)                 # 一条路径最多走 2N 步,组合数上界是 2N
    holes = sorted(set(pts))                # 去重并按 (x,y) 升序,保证 DP 只从前往后转移
    print(count_paths(n, holes))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 04:53
 * update_at: 2026-10-08 04:53
 */
// 登山(roj 1810)
//
// 题意:从 (0,0) 走到 (N,N),每步只能向右 (x+1,y) 或向上 (x,y+1);
//   站在山脊 (x,x) 上时不允许向上走,等价于路径全程满足 x >= y(不越过直线 y = x)。
//   网格中有 C 个不可走的坑,求合法路径数 mod 1e9+7。
//   数据范围:N <= 1e5,C <= 1000,坑点满足 X >= Y,(0,0) 与 (N,N) 一定不是坑。
//
// 算法(O(N + C^2)):
//   1) 反射原理求两点间"不越过 y = x"的路径数(见 ridge_paths)。
//   2) 按"第一次踩到的坑"对路径容斥:first_hit[i] = 走到坑 i 且 i 是首个被踩到的坑的方案数,
//      最终答案 = path((0,0)->(N,N)) - sum first_hit[i] * path(坑 i -> (N,N))。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL;   // 取模模数
const int MAXC = 1005;         // 坑的个数上限 C <= 1000
const int MAXF = 200005;       // 阶乘表长度上限:一条路径最多走 2N 步,2N <= 2e5

struct Point {                 // 一个坑的坐标
    ll x;
    ll y;
};

Point hole[MAXC];              // 所有坑,按 (x,y) 升序排列后使用
ll first_hit[MAXC];            // first_hit[i] = 走到 hole[i] 且 hole[i] 是首个被踩到的坑的路径数

ll fac[MAXF];                  // fac[i] = i!
ll inv_fac[MAXF];              // inv_fac[i] = (i!)^(-1) mod MOD

// 快速幂:求 a^b mod MOD
ll power_mod(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

// 坑的排序规则:先按横坐标 x,再按纵坐标 y
bool cmp_hole(const Point &a, const Point &b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

// 组合数 C(total, pick) mod MOD,下标越界一律返回 0
ll comb(ll total, ll pick) {
    if (pick < 0 || pick > total || total < 0) return 0;
    return fac[total] * inv_fac[pick] % MOD * inv_fac[total - pick] % MOD;
}

// 从 (sx,sy) 走到 (tx,ty)、全程满足 x >= y 的路径数
// 总数 C(dx+dy, dx);越过直线 y = x+1 的非法路径由反射原理与"终点关于 y=x+1 的对称点
// (ty-1, tx+1)"一一对应,故非法数为 C(dx+dy, ty-sx-1)(组合下标非法时该项为 0)。
ll ridge_paths(ll sx, ll sy, ll tx, ll ty) {
    if (tx < sx || ty < sy) return 0;                    // 终点在起点左下方,不可达
    ll total = (tx - sx) + (ty - sy);                    // 总步数
    ll all = comb(total, tx - sx);                       // 不做界限约束的路径数
    ll bad = (ty > sx) ? comb(total, ty - sx - 1) : 0;   // 反射项;ty <= sx 时必无非法路径
    return (all - bad + MOD) % MOD;
}

// 预处理 0..limit 的阶乘与阶乘逆元,使任意组合数 O(1) 得出
void build_factorials(int limit) {
    fac[0] = 1;
    for (int i = 1; i <= limit; i++) fac[i] = fac[i - 1] * (ll)i % MOD;
    inv_fac[limit] = power_mod(fac[limit], MOD - 2);
    for (int i = limit - 1; i >= 0; i--) inv_fac[i] = inv_fac[i + 1] * (ll)(i + 1) % MOD;
}

// 按 (x,y) 升序排坑(保证坑之间只可能从前往后走,DP 无环),并去掉重复点
int sort_and_unique_holes(int c) {
    sort(hole, hole + c, cmp_hole);
    int m = 0;
    for (int i = 0; i < c; i++) {
        if (m > 0 && hole[m - 1].x == hole[i].x && hole[m - 1].y == hole[i].y) continue;
        hole[m++] = hole[i];
    }
    return m;
}

// 按"首个被踩到的坑"容斥:返回从 (0,0) 到 (N,N) 且不经过任何坑的合法路径数
ll count_paths(ll n, int m) {
    for (int i = 0; i < m; i++) {
        ll ways = ridge_paths(0, 0, hole[i].x, hole[i].y);   // 先算无视其他坑的方案数
        for (int j = 0; j < i; j++) {
            if (hole[j].y > hole[i].y) continue;             // 坑 j 不可能出现在通往坑 i 的路上
            ll tail = ridge_paths(hole[j].x, hole[j].y, hole[i].x, hole[i].y);
            ways = (ways - first_hit[j] * tail) % MOD;       // 扣除"首个坑是 j、随后走到 i"的方案
        }
        first_hit[i] = (ways % MOD + MOD) % MOD;
    }

    ll ans = ridge_paths(0, 0, n, n);
    for (int i = 0; i < m; i++) {
        ll tail = ridge_paths(hole[i].x, hole[i].y, n, n);
        ans = (ans - first_hit[i] * tail) % MOD;
    }
    return (ans % MOD + MOD) % MOD;
}

int main() {
    ll n = 0;
    int c = 0;
    if (scanf("%lld %d", &n, &c) != 2) return 0;   // 输入不合法直接退出
    for (int i = 0; i < c; i++) {
        scanf("%lld %lld", &hole[i].x, &hole[i].y);
    }

    build_factorials((int)(2 * n + 1));
    int m = sort_and_unique_holes(c);
    printf("%lld\n", count_paths(n, m));
    return 0;
}

复杂度

  • 预处理阶乘与逆元:O(N)O(N) 时间、O(N)O(N) 空间。
  • 排序去重:O(Clog⁡C)O(C \log C)。
  • 容斥 DP:O(C2)O(C^2) 次 O(1)O(1) 转移。
  • 总计 O(N+C2)O(N + C^2) 时间、O(N+C)O(N + C) 空间。取 N=105, C=1000N = 10^5,\ C = 1000 时约 1.1×1061.1 \times 10^6 次运算, 远低于 1 s 限制;阶乘表用 long long 存两份共约 3 MB,远低于 128 MB。

总结

本题的关键是把"山脊不能向上走"翻译成 x⩾yx \geqslant y 的线性界限,这样两条约束就都 能用组合数学处理:界限用反射原理 O(1)O(1) 消掉,障碍用按首次踩坑的容斥降维到 O(C2)O(C^2)。 NN 与 CC 量级相差极大(10510^5 vs 10310^3)是提示"以障碍为状态、而非以格子为状态"的信号, 这与"大值域 + 少量特殊点"一类题目的通用套路一致。特判上只要守住反射项下标非法时为 00 (C=0C=0 时答案退化为卡特兰数 Cat(N)\mathrm{Cat}(N)),边界就不会出错。

数据说明:本题素材包自带数据生成脚本 data.py,10 个测试点为分层构造 (含 C=0C=0 的卡特兰数点、N=1N=1 边界点、以及 C=1000C=1000 的链式障碍最坏点), 属仓库自造数据;题面为按原题重建,出题意图以题面描述为准。