Submission #19919209


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)
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
Task C - Robot on Grid
User oniku
Language PyPy3 (7.3.0)
Score 500
Code Size 1308 Byte
Status AC
Exec Time 2708 ms
Memory 471544 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 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