/ 
実行時間制限: 6 sec / メモリ制限: 1024 MiB
配点 : 650 点
問題文
縦 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 で割った余りを求めてください。
制約
- 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:
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