C - Robot on Grid Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

H 行 W 列のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と書くことにします。 それぞれのマスには R, D, X のいずれかの文字を書き込むことができます。はじめ、どのマスにも文字は書き込まれていません。

すぬけ君は K 個のマスを選んで文字を書き込みました。 i 番目に文字を書き込んだマスは (h_i,w_i) で、書き込んだ文字は c_i でした。

残りのマスへの文字の書き込み方は 3^{HW-K} 通りあります。それぞれの場合について以下の問題の答えを計算し、その総和を 998244353 で割ったあまりを求めてください。

上記のマス目上を移動可能なロボットがあります。 ロボットは (i,j) にいるとき、(i+1,j),(i,j+1) のいずれかに移動することができます。 ただし、(i,j) に R と書かれていた場合は (i,j+1) にのみ、D と書かれていた場合は (i+1,j) にのみ移動することができます。X と書かれていた場合はどちらにも移動可能です。

ロボットを (1,1) に設置したとき、ロボットがマス目の外に出ずに (H,W) に到達するようなロボットの移動経路は何通りありますか？ただし、ロボットは (H,W) に到達した時点で停止するものとします。

ここで、2 つの移動経路が異なるとはロボットが通ったマスの集合が異なることをいいます。

制約

  • 2 \leq H,W \leq 5000
  • 0 \leq K \leq \min(HW,2 \times 10^5)
  • 1 \leq h_i \leq H
  • 1 \leq w_i \leq W
  • i \neq j ならば (h_i,w_i) \neq (h_j,w_j)
  • c_i は R, D, X のいずれか

入力

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

H W K
h_1 w_1 c_1
\vdots
h_K w_K c_K

出力

答えを出力せよ。

入力例 1

2 2 3
1 1 X
2 1 R
2 2 R

出力例 1

5
  • (1,2) のみまだ文字が書き込まれていません。
    • R を書いたとき、ロボットが (H,W) に到達するようなロボットの移動経路は 1 通りです。
    • D を書いたとき、ロボットが (H,W) に到達するようなロボットの移動経路は 2 通りです。
    • X を書いたとき、ロボットが (H,W) に到達するようなロボットの移動経路は 2 通りです。
  • これらの総和である 5 を出力してください。

入力例 2

3 3 5
2 3 D
1 3 D
2 1 D
1 2 X
3 1 R

出力例 2

150

入力例 3

5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

出力例 3

139923295
  • 998244353 で割ったあまりを求めるのを忘れずに。

Score : 500 points

Problem Statement

We have a grid with H rows and W columns of squares. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. On each square, we can write a letter: R, D, or X. Initially, every square is empty.

Snuke chose K of the squares and wrote characters on them. The i-th square he chose was (h_i,w_i), and he wrote the letter c_i on it.

There are 3^{HW-K} ways to write a letter on each of the remaining squares. Find the sum of the answers to the problem below for all those 3^{HW-K} ways, modulo 998244353.

We have a robot that can walk on the grid. When it is at (i,j), it can move to (i+1, j) or (i, j+1).
However, if R is written on (i, j), it can only move to (i, j+1); if D is written on (i, j), it can only move to (i+1, j). If X is written on (i, j), both choices are possible.

When the robot is put at (1, 1), how many paths can the robot take to reach (H, W) without going out of the grid? We assume the robot halts when reaching (H, W).

Here, we distinguish two paths when the sets of squares traversed by the robot are different.

Constraints

  • 2 \leq H,W \leq 5000
  • 0 \leq K \leq \min(HW,2 \times 10^5)
  • 1 \leq h_i \leq H
  • 1 \leq w_i \leq W
  • (h_i,w_i) \neq (h_j,w_j) for i \neq j.
  • c_i is R, D, or X.

Input

Input is given from Standard Input in the following format:

H W K
h_1 w_1 c_1
\vdots
h_K w_K c_K

Output

Print the answer.

Sample Input 1

2 2 3
1 1 X
2 1 R
2 2 R

Sample Output 1

5
  • Only (1,2) is empty.
    • If we write R on it, there is one way that the robot can take to reach (H, W).
    • If we write D on it, there are two ways that the robot can take to reach (H, W).
    • If we write X on it, there are two ways that the robot can take to reach (H, W).
  • We should print the sum of these counts: 5.

Sample Input 2

3 3 5
2 3 D
1 3 D
2 1 D
1 2 X
3 1 R

Sample Output 2

150

Sample Input 3

5000 5000 10
585 1323 R
2633 3788 X
1222 4989 D
1456 4841 X
2115 3191 R
2120 4450 X
4325 2864 X
222 3205 D
2134 2388 X
2262 3565 R

Sample Output 3

139923295
  • Be sure to compute the sum modulo 998244353.