← 返回题目列表

AtCoder · abc357_g

G. 阶梯状网格

中文机器翻译题面 查看原题

分数: 650 点

问题陈述

有一个特殊的网格 N 行。 (N 是偶数。) i从顶部开始的第行有 从左端开始的 \left \lceil \frac{i}{2} \right \rceil \times 2 单元格。
例如,当 N = 6,网格如下所示:

image

让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
每个单元格要么是空单元格,要么是壁单元格。有 M 壁细胞,以及 i第壁细胞是 (a_i, b_i)。在这里, (1, 1) 和 (N, N) 为空。
从 (1, 1),有多少种方式可以到达 (N, N) 通过重复向右或向下移动到相邻的空单元格?求计数模数 998244353.

约束

  • 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).
  • (a_i, b_i) \neq (a_j, b_j) if i \neq j.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

输出

打印到达方式的数量 (N, N) 来自 (1, 1) 通过重复向右或向下移动到相邻的空单元格,模 998244353.


示例输入 1

4 2
2 1
4 2

示例输出 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)

示例输入 2

6 3
2 1
3 3
4 2

示例输出 2

0

示例输入 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

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

示例输出 4

175892766