题目描述

给你大小为的棋盘那就有个格点，你要从左下点走到右上点问方案数，每次只能往上或者往右走。而且这个棋盘里面存在个格点无法走入。

Solution

首先看，当，是可以通过二维的求解过程，这个过河卒问题很基础我就不多解释了，遇到障碍跳过即可。

重点看后面很大，但是会发现他们的很小很小，最多只有 3 个障碍，那么我们知道，如果不存在障碍的情况下，假设要往上走步，往下走步，过河卒从左下往右上走的方案数是。怎么来的，就是一共需要走步可以到终点，这些步骤里面，要选出步进行上移操作，那么剩下步里面只能选择右移了。那么知道怎么计算从左下点到右上点的方案数之后，我们就可以找到新的方案去转移了。

我们假设是从走到第个障碍的合法方案数，这里我们首先需要按更小的尽可能放在前面，更小的也要尽可能放在更大的前面，当然的相对关系没什么必要比较，只需要保证和有一个比之前的点大，我就应该把这个点放在刚刚找到的之前的点后面，这也是我们减掉不合法路径的来源。我们知道如果一个障碍点前面没有新的障碍点，那么它的方案数很容易计算，就是把他看成右上点计算一下即可，但是如果一个点，他曾经走过的路径上会有障碍点，这样的路径是不能计算的，也就是同时都小于当前障碍点的前驱障碍点。通过这个障碍点产生的路径数是不合法的需要减掉。那么假设前驱障碍点是，现在遍历到的是，那么之前我们一定计算出了的值，就是从起点到第个障碍点的方案数，那么一定要经过这个点去到第个障碍点的方案数就是，乘上以第个障碍点为起点，第个障碍点为终点的过河卒方案数。依次减掉即可，为了求解方便我们可以假设目标位置是一个障碍点，这样转移到最后一个障碍点的时候就会求到目标位置的合法方案数。

）比较需要注意的是，这个题目的坐标是一个左上点。。需要特别小心一点。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
const int M = 1e3 + 7;

int n, m, k;
ll dp[M][M], jc[N << 1], inv[N << 1];
bool mp[M][M];
struct Node {
    int x, y;
    bool operator < (const Node& opt) const {
        return x < opt.x or y < opt.y;
    }
}a[N];

void init() { // 线性逆元
    jc[0] = 1;
    rep(i, 1, 2 * N - 1)
        jc[i] = jc[i - 1] * i % MOD;
    inv[2 * N - 1] = qpow(jc[2 * N - 1], MOD - 2, MOD);
    for (int i = 2 * N - 2; ~i; --i)
        inv[i] = inv[i + 1] * (i + 1) % MOD;
}

void DP() {
    dp[0][1] = 1;
    rep(i, 1, k)    mp[a[i].x][a[i].y] = 1;
    rep(i, 1, n) {
        rep(j, 1, m) {
            if (mp[i][j])    continue;
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
        }
    }
    print(dp[n][m]);
}

ll C(int n, int m) {
    return jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}
ll calc(int x, int y) {
    return C(x + y, x);
}

void solve() {
    n = read() + 1, m = read() + 1, k = read();
    rep(i, 1, k)
        a[i].x = n - read() + 1, a[i].y = read();
    if (n < M and m < M) { DP();    return; }
    init();
    a[++k] = { n,m };
    sort(a + 1, a + 1 + k);
    ll ans[5];
    rep(i, 1, k) {
        ans[i] = calc(a[i].x - 1, a[i].y - 1);
        rep(j, 1, i - 1) {
            if (a[j].x < a[i].x and a[j].y < a[i].y)
                ans[i] -= ans[j] * calc(a[i].x - a[j].x, a[i].y - a[j].y) % MOD,
                ans[i] = (ans[i] + MOD) % MOD;
        }
    }
    print(ans[k]);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}