1 条题解
-
0
[Y] Grid 2(dp_y)题解
题意简述
网格( 达 ), 个墙格。从 只向右/下走到 ,求路径数 。
思路
网格太大,不能逐格 DP
可达 ,但墙只有 个。于是只对墙做容斥。
无障碍的路径数
从 到 ()只向右/下走的路径数为
预处理阶乘到 即可 计算。
容斥 DP
把墙按 排序。设 = 从 到第 个墙格、且不经过任何更早的墙的方案数(即"合法到达该墙"的方案数):
$$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}.$$前半是"总共能到达的路径数",后半是"第一次碰到墙就撞在第 个墙上的路径数"。相减即"不经过任何墙"。
最后把终点当作一个额外的"墙",同样容斥:
$$\text{ans} = \binom{H+W-2}{H-1} - \sum_{j} f_j \cdot \binom{(H-r_j)+(W-c_j)}{H-r_j}.$$复杂度
时间 , 时 ,可行;空间 。
参考代码
#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; }易错点
- 阶乘要预处理到 (),不是 。
- 容斥时
v -= ...会变负,最后要(x % MOD + MOD) % MOD。 - 只统计 且 的前驱(否则不可能从 走到 )。
- 排序后同一行/同一列的墙要正确处理(排序保证前面的 ,但仍要判断 )。
- 起终点保证不是墙,所以不用特判。
数据说明
共 15 组:4 组官方样例(含 、);/ 的小规模墙;、、 随机墙;、 随机墙、首行墙、集中在小区域的墙、另一组随机墙。
- 1
信息
- ID
- 34
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者