#C. Robot on Grid

    Type: Default 1000ms 256MiB

Robot on Grid

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Robot on Grid

题目描述

HHWW 列的格点。第 ii 行第 jj 列的格记为(i,j)(i,j)。每个格子都可以填入 RR,DD,XX 中的任意一个字符。一开始每个格子都没有字符。一开始有 KK 个格填入了字符。第 ii 个写入文字的格是(hi,wi)(h_i,w_i),填入的字符是 cic_i

有一个可在上述网格上移动的机器人。机器人在 (i,j)(i,j)时,可以移动到 (i+1,j)(i+1,j)(i,j+1)(i,j+1)中的任意一个。但是,如果(i,j)(i,j)中写着 RR,则只能向(i,j+1)(i,j+1)移动,如果写着 DD,则只能向(i+1,j)(i+1,j)移动。写着 XX 的情况下都可以任意移动。当机器人的起点是 (1,1)(1,1) 时,机器人不出网格而到达 (H,W)(H,W) 的移动路径有几条?

在剩下的格子里填入字符的方法有 3HWK 3^{HW-K} 种,请输出所有填字符情况下路径条数的总和,模 998244353998244353 的结果。

问题:

输入格式

第一行三个整数 H,W,KH,W,K ,接下来 KK 行每行两个数字 hi,wih_i,w_i 和一个字符 cic_i

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

5

样例 #2

样例输入 #2

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

样例输出 #2

150

样例 #3

样例输入 #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

数据范围

  • 2  H,W  5000 2\ \leq\ H,W\ \leq\ 5000
  • 0  K  min(HW,2 × 105) 0\ \leq\ K\ \leq\ \min(HW,2\ \times\ 10^5)
  • 1  hi  H 1\ \leq\ h_i\ \leq\ H
  • 1  wi  W 1\ \leq\ w_i\ \leq\ W
  • i  j i\ \neq\ j 时必有 (hi,wi)  (hj,wj) (h_i,w_i)\ \neq\ (h_j,w_j)
  • ci c_i R, D, X 之一

样例解释 1

  • (1,2) (1,2) 22 种情况。
  • R 时、到 (H,W) (H,W) 的路径只有 1 1 种。
  • D 或者 X 时、到 (H,W) (H,W) 的路径各有 2 2 种。
  • 故总数是 5 5

20240611集训

Not Attended
Status
Done
Rule
IOI
Problem
6
Start at
2024-6-11 19:00
End at
2024-6-11 21:00
Duration
2 hour(s)
Host
Partic.
14