题意

有一个 $n \times m$ 的棋盘，有 $k$ 个危险格子。有一个初始在 $(1,1)$ 的小兵。小兵每次可以选择从 $(x,y)$ 走到 $(x+1,y),(x,y+1),(x+1,y+1)$ 三个格子中的一个。小兵不能经过危险格子。当小兵从网格上方或网格右方走出棋盘时，小兵停止移动。求小兵走出棋盘的方案数，模 $59393$。

$\text{ps:}$走出棋盘的那一步，即最后一步，走法不同也是不同方案。即从 $(1,m)$ 走到 $(2,m+1)$ 和 $(1,m+1)$ 是两种方案。

$1 \le n \le 10^9,1 \le m \le 10^5,0 \le k \le 20$

分析

首先，这个结束方式不好算，考虑转化。我们可以给网格变成 $(n+1) \times (m+1)$ 的，让小兵在不走出网格的前提下走到 $(n+1,m+1)$。

接下来计算。先不考虑危险格子的影响，如果求从 $(1,1)$ 走到 $(n+1,m+1)$ 的方案数怎么算？

在正常的过河卒问题中，我们可以知道一定是走了 $n$ 步向上和 $m$ 步向右。但是这里会有右上方的走法，所以可以枚举右上方的个数。设 $f(n,m)$ 表示从 $(1,1)$ 走到 $(n+1,m+1)$ 的方案数。

$$f(n,m) = \sum_{i=0}^{\min(n,m)} C_{n+m-i}^i \times C_{n+m-2i}^{n-i}$$

然后考虑危险格子。我们可以容斥。因为 $k$ 只有 $20$，我们枚举经过哪些危险格子。然后计算经过这些格子的方案数。这个是容易的，假设这些格子按 $x$ 为第一关键字，$y$ 为第二关键字排序之后依次是 $(x_1,y_1),(x_2,y_2)\dots(x_t,y_t)$。

$$\prod_{i=2}^t f(x_i - x_{i-1},y_i - y_{i-1})$$

记这个为 $res$，则答案就是 $\sum res \times (-1)^t$。

先预处理出两个点的走的方案数，时间复杂度为 $O(mk^2)$。然后枚举，时间复杂度是 $O(k \times 2^k)$。所以时间复杂度是 $O(k \times 2^k + mk^2)$。

但是注意，算组合数的时候，因为模数很小，所以要用 $\text{Lucas}$ 定理。

#include <bits/stdc++.h>
using namespace std;
#define il inline
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
const int P = 59393;
int n, m, k, fact[P], inv_fact[P], dis[25][25], t[25];
struct T{
    int x, y;
}p[25];
il bool cmp(T x, T y){return x.x != y.x ? x.x < y.x : x.y < y.y;}
il int ksm(int x, int r, int P){
    int ans = 1;
    for (; r; x = 1ll * x * x % P, r >>= 1) if (r & 1) ans = 1ll * ans * x % P;
    return ans;
}
int C(int n, int m, int P){return (n < m ? 0 : 1ll * fact[n] * inv_fact[m] % P * inv_fact[n - m] % P);}
int Lcs(int n, int m, int P){return (n < m ? 0 : !n ? 1 : 1ll * Lcs(n / P, m / P, P) * C(n % P, m % P, P) % P);}
int f(int n, int m){
    int ans = 0;
    for (int i = 0; i <= min(n, m); i++) ans = (ans + 1ll * Lcs(n + m - i, i, P) * Lcs(n + m - i - i, n - i, P) % P) % P;
    return ans;
}
int main(){
    n = rd(), m = rd(), k = rd(), fact[0] = 1;
    for (int i = 1; i <= k; i++) p[i] = T{rd(), rd()};
    sort (p + 1, p + k + 1, cmp);
    for (int i = 1; i < P; i++) fact[i] = 1ll * fact[i - 1] * i % P;
    inv_fact[P - 1] = ksm(fact[P - 1], P - 2, P);
    for (int i = P - 2; i >= 0; i--) inv_fact[i] = 1ll * inv_fact[i + 1] * (i + 1) % P;
    int ans = 0;
    p[0] = T{1, 1}, p[k + 1] = T{n + 1, m + 1};
    for (int i = 0; i <= k + 1; i++) for (int j = i + 1; j <= k + 1; j++) dis[i][j] = f(p[j].x - p[i].x, p[j].y - p[i].y);
    for (int s = 0; s < (1 << k); s++){
        int cnt = 0, res = 1;
        t[++cnt] = 0;
        for (int i = 1; i <= k; i++) if ((s >> (i - 1)) & 1) t[++cnt] = i;
        t[++cnt] = k + 1;
        for (int i = 2; i <= cnt; i++) res = 1ll * res * dis[t[i - 1]][t[i]] % P;
        ans = ((cnt & 1) ? (ans - res + P) : (ans + res)) % P;
    }
    printf ("%d\n", ans);
    return 0;
}