类型为含有多个禁止位置的路线问题

h行w列矩阵，从左上角出发，只能向右或下走，且有n个禁止位置，求到右下角的路线数

\(1 \leq h, w \leq 10^5, 1 \leq n \leq 2000\)

容斥，对禁止位置排序，考虑到达第i个禁止位置的不经过其他禁止位置的路线，它可以通过容斥，用前i-1个更新。

复杂度\(O(n^2)\)

#include 
    
     #include 
     
      #include 
      
       #define MOD 1000000007using namespace std;typedef long long LL;int h, w, n;const int maxn = 2e3 + 10;const int maxhw = 2e5 + 10;LL ans[maxn];int fact[maxhw], inv[maxhw], INV[maxhw];struct node {    int x; int y;} pn[maxn];bool cmp(const node& A, const node& B) {    return A.x == B.x ? A.y < B.y : A.x < B.x;}void init() {    fact[0] = fact[1] = 1;    inv[0] = inv[1] = 1;    INV[0] = INV[1] = 1;    for (int i = 2; i < maxhw; i++) {        fact[i] = (LL)fact[i - 1] * i % MOD;        inv[i] = (LL)(MOD - MOD / i) * inv[MOD % i] % MOD;        INV[i] = (LL)inv[i] * INV[i - 1] % MOD;    }}int main() {    init();    scanf("%d%d%d", &h, &w, &n);    for (int i = 0; i < n; i++) {        scanf("%d%d", &pn[i].x, &pn[i].y);    }    sort(pn, pn + n, cmp);    pn[n].x = h; pn[n].y = w;     for (int i = 0; i <= n; i++) {        int x = pn[i].x; int y = pn[i].y;        ans[i] = (LL)fact[x + y - 2] * INV[x - 1] % MOD * INV[y - 1] % MOD;        for (int j = 0; j < i; j++) {            int nx = pn[j].x, ny = pn[j].y;            if (nx > x || ny > y) continue;            ans[i] = (ans[i] - ans[j]                          * fact[x - nx + y - ny] % MOD                         * INV[x - nx] % MOD                         * INV[y - ny] % MOD                    ) % MOD;        }    }    printf("%lld\n", (ans[n] + MOD) % MOD);    return 0;}