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