P5376 [THUPC 2019] 过河卒二

题目描述

首先我们回忆一下经典难题过河卒问题：

棋盘上 $A$ 点有一个过河卒，需要走到目标 $B$ 点。卒行走的规则：可以向上、或者向右。同时在棋盘上 $C$ 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点，因此称之为「马拦过河卒」。

棋盘用坐标表示，$A$ 点 $(1,1)$ 、$B$ 点 $(N,M)$ ，同样马的位置坐标是需要给出的。

现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

请注意，上述背景内容与本题无关！

Kiana 喜欢玩象棋，尤其是喜欢用象棋玩过河卒的游戏。在传统的过河卒问题中，Kiana 需要控制一个卒从起点走到终点，在路中避开一个对方的马的攻击，然后假装不会算并询问你从起点到终点的路径总数。

在今天的过河卒二游戏中，Kiana 还是控制一个卒在一个 $N\times M$ 的棋盘上移动，初始时卒位于左下方坐标为 $(1,1)$ 位置，但为了增加难度，Kiana 对游戏规则做出了一些修改。传统的过河卒每步只能向上或向右移动 $1$ 格，Kiana 规定自己的过河卒二还可以在一步中向右上方移动 $1$ 格，即如果当前卒位于坐标 $(x,y)$ 处，则下一步可以走到 $(x+1,y)$ 、$(x,y+1)$ 或 $(x+1,y+1)$ 中的任意一格里面去，同时 Kiana 认为，如果两种移动方案在某一步时卒移动的方向（右、上或右上）不同，则两种方案就是不同的，例如从 $(1,1)$ 先走到 $(1,2)$ 再走到 $(2,2)$ 、从 $(1,1)$ 先走到 $(2,1)$ 再走到 $(2,2)$ 和从 $(1,1)$ 直接走到 $(2,2)$ 是三种不同的移动方案。

其次，过河卒二的终点不再是一个特定的位置，Kiana 规定卒可以从棋盘的上方或右方走出棋盘，此时就视为游戏成功。注意在走出棋盘时仍然有方向选择的不同，例如若过河卒位于 $(1,M)$ 处，则下一步它可以向右或者向右上用两种方式走出棋盘，若过河卒位于 $(N,M)$ 处，则下一步它可以向上、向右或者向右上用三种方式走出棋盘，以不同的方式走出棋盘仍然被算作是不同的移动方案。

此外，对方马的攻击范围不再是有规律的几个位置，而是 Kiana 规定好的 $K$ 个特定坐标，并要求过河卒在移动的过程中不能走到这 $K$ 个坐标的任何一个上，在除这些坐标以外的位置上过河卒都可以按规则自由移动。

现在 Kiana 想知道，过河卒二有多少种不同的移动方案可以走出棋盘，这个答案可能非常大，她只想知道方案数对 $59393$ 取模后的结果。由于她不会算，所以希望由你来告诉她。

输入格式

第一行包含三个整数 $N$ 、$M$ 和 $K$ ，分别表示棋盘的坐标范围与对方马的攻击格子数（即 Kiana 规定的不能经过的坐标数）。

接下来 $K$ 行，第 $i$ 行包含两个正整数 $X_i$ 和 $Y_i$ ，表示对方马的第 $i$ 个攻击坐标为 $(X_i,Y_i)$ 。

对于所有数据，保证 $1\le N\le {10}^9,1\le M\le {10}^5,0\le K\le 20,1\le X_i\le N,1\le Y_i\le M$，$(1,1)$ 一定不会被对方马攻击，且被攻击的格子中不存在两个坐标相同的格子。

输出格式

输出一行一个整数，表示过河卒走出棋盘的方案数对 $59393$ 取模后的结果。

输入输出样例 #1

输入 #1

3 3 1
2 2

输出 #1

24

说明/提示

样例解释

用 $\uparrow$ 表示过河卒向上移动了一格，用 $\to$ 表示过河卒向右移动了一格，用 $\nearrow$ 表示过河卒向右上移动了一格，由此可以简化样例解释的表述。

$24$ 种移动方案如下：

$(\uparrow \uparrow \uparrow )$、$(\uparrow \uparrow \nearrow )$、$(\uparrow \uparrow \to \uparrow )$、$(\uparrow \uparrow \to \nearrow )$、

$(\uparrow \uparrow \to \to \uparrow )$、$(\uparrow \uparrow \to \to \nearrow )$、$(\uparrow \uparrow \to \to \to )$、$(\uparrow \nearrow \uparrow )$、

$(\uparrow \nearrow \nearrow )$、$(\uparrow \nearrow \to \uparrow )$、$(\uparrow \nearrow \to \nearrow )$、$(\uparrow \nearrow \to \to )$、

$(\to \to \to )$、$(\to \to \nearrow )$、$(\to \to \uparrow \to )$、$(\to \to \uparrow \nearrow )$、

$(\to \to \uparrow \uparrow \to )$、$(\to \to \uparrow \uparrow \nearrow )$、$(\to \to \uparrow \uparrow \uparrow )$、$(\to \nearrow \to )$、

$(\to \nearrow \nearrow )$、$(\to \nearrow \uparrow \to )$、$(\to \nearrow \uparrow \nearrow )$、$(\to \nearrow \uparrow \uparrow )$。

版权信息

来自 THUPC（THU Programming Contest，清华大学程序设计竞赛）2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。

题解

对于一般的网格行走问题，$(0,0)\to (n,m)$ 的方案数是 $C_{n+m}^n$。

现在我们还可以沿着斜对角走，我们枚举斜着走 $i$ 步，则由插板法：

$$f(n,m)=\sum _{i=0}^{min(n,m)}{C}_{n+m-i}^i\cdot C_{n+m-2i}^{n-i}$$

在本题中，过河卒二的终点不再是一个特定的位置，Kiana 规定卒可以从棋盘的上方或右方走出棋盘，此时就视为游戏成功。注意在走出棋盘时仍然有方向选择的不同。显然该限制的方案数等价于 $(1,1)\to (n+1,m+1)$ 的方案数，因为从“走出棋盘”到“走到 $(n+1,m+1)$”的方案是唯一的。

关于棋盘中障碍物的处理，是一个典型的容斥原理问题。我们预处理处任意两个障碍物 $(i,j)$ 之间的方案数：

$$g(i,j)=C_{x_j-x_i+y_j-y_i}^{x_j-x_i}$$

计所有障碍的集合为 $T$，$calc(S)$ 为 $(1,1)\to (n+1,m+1)$ 且经过集合 $S$ 中所有障碍的方案数，则最终答案为：

$$\sum _{S\subseteq T}calc(S)\times (-1^{|S|})$$

由于模数是质数，可以用 Lucas 定理计算：

$$C_{sp+q}^{tp+r}=C_s^t{C}_q^r(\text{mod }p)$$