ソースコード 拡げる

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)
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)
```

#### 提出情報

提出日時 2021-02-04 22:55:36+0900 C - Robot on Grid oniku PyPy3 (7.3.0) 500 1308 Byte AC 2708 ms 471544 KB

#### ジャッジ結果

セット名 Sample All

 AC × 3
 AC × 21
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
random_01.txt AC 303 ms 70424 KB
random_02.txt AC 94 ms 70716 KB
random_03.txt AC 95 ms 70336 KB
random_04.txt AC 94 ms 70320 KB
random_05.txt AC 2692 ms 471532 KB
random_06.txt AC 2697 ms 471328 KB
random_07.txt AC 2708 ms 471484 KB
random_08.txt AC 2688 ms 471544 KB
random_09.txt AC 2703 ms 471320 KB
random_10.txt AC 2690 ms 471516 KB
random_11.txt AC 133 ms 71048 KB
random_12.txt AC 123 ms 71008 KB
random_13.txt AC 111 ms 70408 KB
random_14.txt AC 123 ms 71236 KB
random_15.txt AC 120 ms 70960 KB
random_16.txt AC 450 ms 123576 KB
random_17.txt AC 1075 ms 247168 KB
random_18.txt AC 1235 ms 462500 KB
sample_01.txt AC 103 ms 69856 KB
sample_02.txt AC 81 ms 69768 KB
sample_03.txt AC 1215 ms 462664 KB