路径受 y≤x 的山脊界限约束,用反射原理 O(1) 求两点间受限路径数,再按首次踩到的坑做容斥 DP,复杂度 O(N+C^2)。
OJ: roj
题目 ID: 1810
难度:普及+/提高-
标签:数学组合数学容斥反射原理
创建: 2026-10-08 04:53
更新: 2026-10-08 04:53
形式化题目
给出整数
"在
即路径全程不越过直线
正解
思路
第一步:两点间的受限路径数。 先不管障碍,只要求从
当
第二步:按"首次踩到的坑"容斥。 把所有坑按
无视其他坑先算出
(只需检查
最后把整个终点也看成"第
每一步都只用到
代码
#!/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()/**
* 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;
}复杂度
- 预处理阶乘与逆元:
时间、 空间。 - 排序去重:
。 - 容斥 DP:
次 转移。 - 总计
时间、 空间。取 时约 次运算, 远低于 1 s 限制;阶乘表用 long long存两份共约 3 MB,远低于 128 MB。
总结
本题的关键是把"山脊不能向上走"翻译成
数据说明:本题素材包自带数据生成脚本
data.py,10 个测试点为分层构造 (含的卡特兰数点、 边界点、以及 的链式障碍最坏点), 属仓库自造数据;题面为按原题重建,出题意图以题面描述为准。