主要思路

这一道题其实挺好的，我们来分析一下。

首先，我们知道在一个方格纸上，从左上角到右下角的路径的数量是\(C_{H+W-2}^{H-1}\)，可以理解为横向路径的选法总数。之后，我们来进行容斥。在本题中，我们需要容斥掉那些经过了至少一次黑点的路径数量。因为本题中黑点个数小于\(5000\)，所以我们直接来跑一个\(O(n^2)\)的 DP。设\(F[i]\)为经过了此点的路径数，然后我们把右下角的点设为第\(n+1\)个点，最后答案存在\(F[n+1]\)处。我们可以很快得到一个递推式：

\[ F[i] = C_{x_i + y_i – 2}^{x_i – 1} – \sum_{j = 1}^{i-1} (F[j] * C_{x_i-x_j+y_i-y_j}^{x_i-x_j})，且x_i \geq x_j, y_i \geq y_j. \]

解释：对于到点\(i\)的路径，首先不考虑之前的黑点则有\( C_{x_i + y_i – 2}^{x_i – 1} \)种路；而要容斥掉至少经过过一次的黑点的路径，可以直接对于之前的每一个点进行计算，计算之前的点\(j\)到现在的点\(i\)有多少种路径。

代码

// CF559C.cpp
#include <bits/stdc++.h>
#define ll long long
#define pr pair<ll, ll>
using namespace std;
const int MOD = 1e9 + 7, MAX_N = 2020, LEVEL_RG = 200000;
ll level[200010], inv[200010], n, h, w, F[MAX_N];
pr pts[MAX_N];
ll quick_power(ll bas, ll tim, ll mod)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
ll C(ll n, ll m) { return level[n] * inv[n - m] % MOD * inv[m] % MOD; }
int main()
{
    scanf("%d%d%d", &h, &w, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &pts[i].first, &pts[i].second);
    sort(pts + 1, pts + 1 + n);
    pts[n + 1].first = h, pts[n + 1].second = w;
    level[0] = inv[0] = 1;
    for (int i = 1; i <= LEVEL_RG; i++)
        level[i] = level[i - 1] * i % MOD;
    ll inv_bas = quick_power(level[LEVEL_RG], MOD - 2, MOD);
    for (int i = LEVEL_RG; i >= 1; i--)
        inv[i] = inv_bas, inv_bas = inv_bas * i % MOD;
    for (int i = 1; i <= n + 1; i++)
    {
        F[i] = C(pts[i].first + pts[i].second - 2, pts[i].first - 1) % MOD;
        for (int j = 1; j < i; j++)
            if (pts[j].first <= pts[i].first && pts[j].second <= pts[i].second)
                F[i] = (F[i] - F[j] * C(pts[i].first + pts[i].second - pts[j].first - pts[j].second, pts[i].first - pts[j].first)) % MOD;
    }
    printf("%lld", (F[n + 1] + MOD) % MOD);
    return 0;
}