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$ 取模。

4 2
2 1
4 2

2

6 3
2 1
3 3
4 2

0

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

619611437

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

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, 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)$

标签: AtCoder|abc357G

来源

AtCoder|abc357G