結果
問題 | No.2926 Botaoshi |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:14:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 262 ms / 2,000 ms |
コード長 | 2,789 bytes |
コンパイル時間 | 415 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 142,144 KB |
最終ジャッジ日時 | 2024-10-12 16:14:58 |
合計ジャッジ時間 | 8,090 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
import sys, math sys.set_int_max_str_digits(0) inf = 1<<60 MOD = 998244353 class Modint(int): mod = 998244353 def modpow(self, i: int, r: int) -> int: return pow(i, r, Modint.mod) def modinv(self, i: int, r: int = 1) -> int: return pow(i, Modint.mod - 1 - r, Modint.mod) def __add__(self, other): return Modint(int.__add__(self, other) % Modint.mod) def __sub__(self, other): return Modint(int.__sub__(self, other) % Modint.mod) def __mul__(self, other): return Modint(int.__mul__(self, other) % Modint.mod) def __floordiv__(self, other): return Modint(int.__mul__(self, self.modinv(other)) % Modint.mod) __truediv__ = __floordiv__ def __pow__(self, other): return Modint(self.modpow(self, other)) def __radd__(self, other): return Modint(int.__add__(other, self) % Modint.mod) def __rsub__(self, other): return Modint(int.__sub__(other, self) % Modint.mod) def __rmul__(self, other): return Modint(int.__mul__(other, self) % Modint.mod) def __rfloordiv__(self, other): return Modint(int.__mul__(other, self.modinv(self)) % Modint.mod) __rtruediv__ = __rfloordiv__ def __rpow__(self, other): return Modint(self.modpow(other, self)) def __iadd__(self, other): self = self.__add__(other) return self def __isub__(self, other): self = self.__sub__(other) return self def __imul__(self, other): self = self.__mul__(other) return self def __ifloordiv__(self, other): self = self.__mul__(self.modinv(other)) return self def __neg__(self): return (self.mod - self) % self.mod __itruediv__ = __ifloordiv__ def __ipow__(self, other): self = Modint(self.modpow(self, other)) return self N = int(input()) S = ['U'] + list(input()) DP = [[Modint(0)] * (3) for _ in range(N + 1)] # j == 0 : | # j == 1 : \ # j == 2 : / # 初期状態で | が一本たっているとする DP[0][0] = 1 d = {} d['U'] = 0 d['L'] = 1 d['R'] = 2 for i in range(N): if S[i] != '.': srcj = d[S[i]] # DP[i][srcj] からの寄与のみ考える if srcj <= 1: for j in range(3): #dst DP[i + 1][j] += DP[i][srcj] else: for j in [0, 2]: DP[i + 1][j] += DP[i][srcj] else: # '.' だったら全部 for j in range(3): for dstj in range(3): # j == 2 and dstj == 1 のとき以外寄与つくる if j == 2 and dstj == 1: continue DP[i + 1][dstj] += DP[i][j] if S[-1] == '.': ans = sum(DP[-1]) else: ans = DP[-1][d[S[-1]]] print(ans%MOD)