Contest Duration: - (local time) (120 minutes) Back to Home

Submission #19919330

Source Code Expand

Copy
```import sys
from typing import Tuple

sys.setrecursionlimit(10 ** 8)

def extra_gcd(m: int, n: int) -> Tuple[int, int, int]:
if n:
d, b, a = extra_gcd(n, m % n)
b = b - (m // n) * a
return d, a, b

return m, 1, 0

def mod_inv(a: int, b: int) -> int:
d, x, y = extra_gcd(a, b)
if d != 1:
print("modular inverse does not exist")
exit()
else:
return x % b

H, W, K = map(int, input().split())

table = [["0"] * (W + 1) for _ in range(H + 1)]
dp = [[0] * (W + 1) for _ in range(H + 1)]

for _ in range(K):
h, w, c = map(str, input().split())
height: int = int(h) - 1
width: int = int(w) - 1
table[height][width] = c

dp[0][0] = 1
# inv = mod_inv(3, 998244353)
# print(inv)
inv = 332748118
for i in range(H):
for j in range(W):

dp[i][j] %= 998244353

if table[i][j] == "0":
dp[i][j + 1] += dp[i][j] * 2 * inv
dp[i + 1][j] += dp[i][j] * 2 * inv
elif table[i][j] == "X":
dp[i][j + 1] += dp[i][j]
dp[i + 1][j] += dp[i][j]
elif table[i][j] == "R":
dp[i][j + 1] += dp[i][j]
elif table[i][j] == "D":
dp[i + 1][j] += dp[i][j]

print(dp[H - 1][W - 1] * pow(3, H * W - K, 998244353) % 998244353)
```

#### Submission Info

Submission Time 2021-02-04 23:02:18+0900 C - Robot on Grid oniku PyPy3 (7.3.0) 500 1341 Byte AC 2753 ms 471584 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
 AC × 3
 AC × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 116 ms 70528 KB
random_02.txt AC 95 ms 70588 KB
random_03.txt AC 93 ms 70508 KB
random_04.txt AC 96 ms 70484 KB
random_05.txt AC 2731 ms 471492 KB
random_06.txt AC 2732 ms 471556 KB
random_07.txt AC 2728 ms 471540 KB
random_08.txt AC 2751 ms 471584 KB
random_09.txt AC 2742 ms 471484 KB
random_10.txt AC 2753 ms 471544 KB
random_11.txt AC 142 ms 71192 KB
random_12.txt AC 126 ms 71048 KB
random_13.txt AC 113 ms 70524 KB
random_14.txt AC 128 ms 71216 KB
random_15.txt AC 124 ms 70896 KB
random_16.txt AC 475 ms 123560 KB
random_17.txt AC 1090 ms 247192 KB
random_18.txt AC 1236 ms 462776 KB
sample_01.txt AC 108 ms 70196 KB
sample_02.txt AC 86 ms 69832 KB
sample_03.txt AC 1226 ms 462624 KB