AT_abc357_g [ABC357G] Stair-like Grid

题目描述

有一个特殊形状的纵向 $N$ 行的网格（$N$ 为偶数）。从上往下第 $i$ 行，从左端开始有 $\left\lceil \frac{i}{2} \right\rceil \times 2$ 个格子排列。
例如，当 $N=6$ 时，网格形状如下图所示。

从上往下第 $i$ 行、从左往右第 $j$ 列的格子记作 $(i, j)$。
每个格子要么是空格子，要么是墙格子。共有 $M$ 个墙格子，第 $i$ 个墙格子位于 $(a_i, b_i)$。但 $(1, 1)$ 和 $(N, N)$ 一定是空格子。
从 $(1, 1)$ 出发，每次只能移动到右边或下方相邻的空格子，问有多少种不同的路径可以到达 $(N, N)$？请将答案对 $998244353$ 取模后输出。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$

输出格式

输出从 $(1, 1)$ 出发，每次只能移动到右边或下方相邻的空格子，最终到达 $(N, N)$ 的路径数，对 $998244353$ 取模后的结果。

输入输出样例 #1

输入 #1

4 2
2 1
4 2

输出 #1

2

输入输出样例 #2

输入 #2

6 3
2 1
3 3
4 2

输出 #2

0

输入输出样例 #3

输入 #3

100 10
36 9
38 5
38 30
45 1
48 40
71 52
85 27
86 52
92 34
98 37

输出 #3

619611437

输入输出样例 #4

输入 #4

100000 10
552 24
4817 255
7800 954
23347 9307
28028 17652
39207 11859
48670 22013
74678 53158
75345 45891
88455 4693

输出 #4

175892766

说明/提示

限制条件

• $2 \leq N \leq 2.5 \times 10^5$
• $N$ 是偶数
• $0 \leq M \leq 50$
• $1 \leq a_i \leq N$
• $1 \leq b_i \leq \left\lceil \frac{a_i}{2} \right\rceil \times 2$
• $(a_i, b_i) \neq (1, 1)$ 且 $(a_i, b_i) \neq (N, N)$
• 若 $i \neq j$，则 $(a_i, b_i) \neq (a_j, b_j)$
• 所有输入均为整数

样例解释 1

满足题目条件的路径有如下 $2$ 条：

• $(1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3) \to (3, 4) \to (4, 4)$
• $(1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3) \to (4, 3) \to (4, 4)$

由 ChatGPT 4.1 翻译