G - Stair-like Grid Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 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)
  • i \neq j ならば (a_i, b_i) \neq (a_j, b_j)
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

出力

(1, 1) を出発して、右または下に隣り合う空きマスへの移動を繰り返して (N, N) へ辿り着く方法の個数を 998244353 で割った余りを出力せよ。

入力例 1

4 2
2 1
4 2

出力例 1

2

問題文の条件を満たす経路は次の 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

Score : 650 points

Problem Statement

There is a special grid with N rows. (N is even.) The i-th row from the top has \left \lceil \frac{i}{2} \right \rceil \times 2 cells from the left end.
For example, when N = 6, the grid looks like the following:

image

Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
Each cell is either an empty cell or a wall cell. There are M wall cells, and the i-th wall cell is (a_i, b_i). Here, (1, 1) and (N, N) are empty.
Starting from (1, 1), how many ways are there to reach (N, N) by repeatedly moving right or down to an adjacent empty cell? Find the count modulo 998244353.

Constraints

  • 2 \leq N \leq 2.5 \times 10^5
  • N is even.
  • 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) and (a_i, b_i) \neq (N, N).
  • (a_i, b_i) \neq (a_j, b_j) if i \neq j.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
\vdots
a_M b_M

Output

Print the number of ways to reach (N, N) from (1, 1) by repeatedly moving right or down to an adjacent empty cell, modulo 998244353.

Sample Input 1

4 2
2 1
4 2

Sample Output 1

2

There are two paths that satisfy the conditions of the problem:

  • (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)

Sample Input 2

6 3
2 1
3 3
4 2

Sample Output 2

0

Sample Input 3

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

Sample Output 3

619611437

Sample Input 4

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

Sample Output 4

175892766