题目
题目描述
曾经有一道叫做迷雾森林的题目，然而牛牛认为地图中的障碍太多，实在是太难了，所以删去了很多点，出了这道题。
牛牛给出了一个n行m列的网格图
初始牛牛处在最左下角的格点上(n+1,1)，终点在右上角的格点(1,m+1)
现在它想知道，从起点走到终点，只能向上或向右走，一共有多少种走法呢？
需要注意的是，除了起点和终点外，其它的每个格点都有可能有障碍，无法通过。
请注意格子与格点的区别
输入描述
第一行三个整数n,m,k，表示格子的大小，以及有k个障碍
接下来k行（若k=0则无此行），每行一个格点坐标（x,y），表示每个障碍的位置
输出描述
仅一行，一个整数表示答案对998244353取模的值
示例1
输入
4 5 1
3 4
输出
66
说明
示例2
输入
12345 54321 2
123 321
456 654
输出
801071140
示例3
输入
114 514 3
19 19
8 10
65 45
输出
567102428
备注
题解
知识点：计数dp，容斥原理，DAG上dp。
按数据点分治，先将 \(x\) 变换为 \(n+1-x\) ，这样起点就是 \((1,1)\) ，终点就是 \((n+1,m+1)\) 。
当 \(n,m \leq 1000\) 时，就是朴素的路径计数dp，不多讲了。
当 \(n,m > 1000\) 时，注意到 \(k\) 很小，可以考虑容斥原理，求经过至少一个障碍物的路径总数，再用总路径数减去即可，复杂度是 \(O(k \cdot 2^k)\) 的。其中，从 \((x_1,y_1)\) 到 \((x_2,y_2)\) 的全部路径总数为 \(\dbinom{x_2 - x_1 + y_2 - y_1}{x_2 - x_1}\) 。
但我们发现，这里的容斥实际上大部分状态都是不合法的，因为要保证子集的障碍物满足二维偏序，才是一条合法的障碍物路径。然而，我们将障碍物满足的二维偏序图画出来，呈现的一定是个DAG，于是我们可以仿照之前的路径计数dp，再这个DAG上dp。
我们设 \(f_i\) 表示到第 \(i\) 个障碍物但不经过其他障碍物的路径总数。那么 \(f_i\) 等于到达它全部路径总数，减去能到达它的障碍物 \(j\) 的 \(f_j\) 即可。
为了保证在求 \(f_i\) 之前，所有能到达 \(i\) 的障碍物的答案都已经求完了，我们可以建一个DAG图进行拓扑序的dp，但实际上不需要这么做，我们可以仿照二维偏序（逆序对）的方法进行维护。
我们将障碍物按 \(x\) 坐标从小到大排序，这时候就维护了第一维的偏序。之后当我们枚举到 \(i\) ，我们只需要枚举 \(j\) 满足 \(j<i\) 的障碍物即可先保证了第一维的偏序，再检验第二维偏序即可。
最后，我们用总路径数减去所有障碍物的 \(f\) 即可。
时间复杂度 \(O(min\{nm,k^2\})\)
空间复杂度 \(O(nm+k)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;
namespace Number_Theory {
const int N = 2e5 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int fact[N], invfact[N];
void init(int n) {
fact[0] = 1;
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
invfact[n] = qpow(fact[n], P - 2);
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}
}
namespace CNM {
using namespace Number_Theory;
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
}
}
/// 公式法求组合数，O(n)，预处理阶乘及其逆元快速求出组合数
int calc(int x1, int y1, int x2, int y2) {
return CNM::C(x2 - x1 + y2 - y1, x2 - x1);
}
pair<int, int> obst[100007];
bool dt[1007][1007];
int f[1007][1007];
int ans[100007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1;i <= k;i++) {
int x, y;
cin >> x >> y;
obst[i] = { n + 1 - x + 1,y };
}
if (n <= 1000 && m <= 1000) {
for (int i = 1;i <= k;i++) {
auto [x, y] = obst[i];
dt[x][y] = 1;
}
f[0][1] = 1;
for (int i = 1;i <= n + 1;i++)
for (int j = 1;j <= m + 1;j++)
if (!dt[i][j]) f[i][j] = (f[i - 1][j] + f[i][j - 1]) % P;
cout << f[n + 1][m + 1] << '\n';
}
else {
Number_Theory::init(n + m + 2);
sort(obst + 1, obst + k + 1);
obst[++k] = { n + 1,m + 1 };
for (int i = 1;i <= k;i++) {
auto [x1, y1] = obst[i];
ans[i] = calc(1, 1, x1, y1);
for (int j = 1;j <= i - 1;j++) {
auto [x2, y2] = obst[j];
if (x2 > x1 || y2 > y1) continue;
(ans[i] -= 1LL * ans[j] * calc(x2, y2, x1, y1) % P - P) %= P;
}
}
cout << ans[k] << '\n';
}
return 0;
}
