結果
| 問題 |
No.2257 Swim and Sleep
|
| コンテスト | |
| ユーザー |
 shobonvip
|
| 提出日時 | 2023-03-24 05:39:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,637 bytes |
| コンパイル時間 | 175 ms |
| コンパイル使用メモリ | 82,324 KB |
| 実行使用メモリ | 85,364 KB |
| 最終ジャッジ日時 | 2024-09-18 15:52:20 |
| 合計ジャッジ時間 | 6,561 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 6 WA * 11 |
ソースコード
#
# type 5 以外が実装できたよ～
#
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n")+(not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s:self.buffer.write(s.encode("ascii"))
self.read = lambda:self.buffer.read().decode("ascii")
self.readline = lambda:self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda:sys.stdin.readline().rstrip("\r\n")
from math import gcd
from collections import defaultdict
mod = 998244353
# TYPE 1 縦・横のみ
def count_type1(m, rl, x, y, r, w, h, g):
ret = 0
if rl[0] + rl[1] == 0:
d = defaultdict(lambda: -1)
mode = 1
for i in range(m):
if d[y[i]] == -1:
d[y[i]] = r[i]
elif d[y[i]] != r[i]:
mode = 0
break
if mode:
f = len(d)
ret += pow(2, h-f, mod)
ret %= mod
if rl[2] + rl[3] == 0:
d = defaultdict(lambda: -1)
mode = 1
for i in range(m):
if d[x[i]] == -1:
d[x[i]] = r[i]
elif d[x[i]] != r[i]:
mode = 0
break
if mode:
f = len(d)
ret += pow(2, w-f, mod)
ret %= mod
return ret
# TYPE 2 偶数自明 (g = 0 mod 2)
def count_type2(m, rl, x, y, r, w, h, g):
ret = 0
if g % 2 == 0:
for parity in range(2):
d1 = defaultdict(lambda: -1)
d2 = defaultdict(lambda: -1)
mode = 1
for i in range(m):
if r[i] == 0 or r[i] == 1:
# たて
if (x[i] + y[i]) % 2 != parity:
mode = 0
break
if d1[x[i]] == -1:
d1[x[i]] = r[i]
elif d1[x[i]] != r[i]:
mode = 0
break
else:
if (x[i] + y[i]) % 2 != 1 ^ parity:
mode = 0
break
if d2[y[i]] == -1:
d2[y[i]] = r[i]
elif d2[y[i]] != r[i]:
mode = 0
break
if mode:
ret += pow(2, w-len(d1) + h-len(d2), mod)
ret %= mod
return ret
# TYPE 3 (x-y)%g で場合分け
def count_type3(m, rl, x, y, r, w, h, g):
ret = 0
for v in [(1, 3), (0, 2)]:
if rl[v[0]] + rl[v[1]] == 0:
mode = 1
d = defaultdict(int)
for i in range(m):
t = (x[i] - y[i]) % g
if d[t] == -1:
d[t] = r[i]
elif d[t] != r[i]:
mode = 0
break
if mode:
ret += pow(2, g-len(d), mod)
ret %= mod
return ret
# TYPE 4 (x+y)%g で場合分け
def count_type4(m, rl, x, y, r, w, h, g):
ret = 0
for v in [(1, 2), (0, 3)]:
if rl[v[0]] + rl[v[1]] == 0:
mode = 1
d = defaultdict(int)
for i in range(m):
t = (x[i] + y[i]) % g
if d[t] == -1:
d[t] = r[i]
elif d[t] != r[i]:
mode = 0
break
if mode:
ret += pow(2, g-len(d), mod)
ret %= mod
return ret
# TYPE 4.5.1
def count_type451(m, rl, x, y, r, w, h, g):
ret = 0
for v in range(4):
if rl[0] + rl[1] + rl[2] + rl[3] - rl[v] == 0:
ret -= 2
ret %= mod
return ret
# TYPe 4.5.2
def count_type452(m, rl, x, y, r, w, h, g):
ret = 0
if g % 2 == 0:
for p in range(4):
for q in range(4):
if p//2 == q//2: continue
mode = 1
for i in range(m):
t = (x[i] + y[i]) % 2
if t == 0 and r[i] != p:
mode = 0
break
if t == 1 and r[i] != q:
mode = 0
break
if mode:
ret -= 1
ret %= mod
return ret
# 非自明を、つくる
def make_hijimei():
ret = []
for num in range(4 ** 8):
v = num
a = [[0] * 4 for i in range(4)]
rl = [0] * 4
for i in range(8):
t = v % 4
v //= 4
a[i//4][i%4] = t
a[i//4 + 2][(i+2)%4] = t
rl[t] += 2
mode = 1
v = 0
for i in range(4):
if rl[i] == 0:
v = 1
if v:
mode = 0
# 衝突
for i in range(4):
md = -1
for j in range(4):
if a[i][j] == 0 or a[i][j] == 1:
if md == -1:
md = a[i][j]
elif md != a[i][j]:
mode = 0
break
for j in range(4):
md = -1
for i in range(4):
if a[i][j] == 2 or a[i][j] == 3:
if md == -1:
md = a[i][j]
elif md != a[i][j]:
mode = 0
break
if mode == 0:
continue
b = [[0] * 4 for i in range(4)]
for i in range(4):
for j in range(4):
b[i][j] = a[i][j]
for tyr in range(20):
c = [[-1] * 4 for i in range(4)]
for i in range(4):
for j in range(4):
if b[i][j] == 0:
if c[i][(j-1)%4] != -1:
mode = 0
break
c[i][(j-1)%4] = b[i][j]
if b[i][j] == 1:
if c[i][(j+1)%4] != -1:
mode = 0
break
c[i][(j+1)%4] = b[i][j]
if b[i][j] == 2:
if c[(i-1)%4][j] != -1:
mode = 0
break
c[(i-1)%4][j] = b[i][j]
if b[i][j] == 3:
if c[(i+1)%4][j] != -1:
mode = 0
break
c[(i+1)%4][j] = b[i][j]
if mode == 0:
break
b = c
if mode:
ans = 0
m = 16
x = [0] * m
y = [0] * m
r = [0] * m
rl = [0] * 4
for i in range(4):
for j in range(4):
x[i*4 + j] = i
y[i*4 + j] = j
r[i*4 + j] = a[i][j]
rl[a[i][j]] += 1
w = 4
h = 4
g = 4
ans += count_type1(m, rl, x, y, r, w, h, g)
ans += count_type2(m, rl, x, y, r, w, h, g)
ans += count_type3(m, rl, x, y, r, w, h, g)
ans += count_type4(m, rl, x, y, r, w, h, g)
ans += count_type451(m, rl, x, y, r, w, h, g)
ans += count_type452(m, rl, x, y, r, w, h, g)
if ans == 0:
ret.append(a)
return ret
# 実行！
ar = make_hijimei()
"""
cnt = 0
for i in ar:
for j in range(4):
print(*i[j])
cnt += 1
print(cnt)
print()
"""
def count_type5(m, rl, x, y, r, w, h, g):
ret = 0
if g % 4 == 0:
a = [[-1] * 4 for i in range(4)]
mode = 1
for i in range(m):
if a[x[i]%4][y[i]%4] == -1:
a[x[i]%4][y[i]%4] = r[i]
elif a[x[i]%4][y[i]%4] != r[i]:
mode = 0
break
if mode == 0:
return 0
for b in ar:
mode = 1
for i in range(4):
for j in range(4):
if a[i][j] != -1 and a[i][j] != b[i][j]:
mode = 0
break
if mode:
ret += 1
return ret
def solve():
# 順番逆のほうが直感的なので逆にしてます（ごめんね）
w, h, m = map(int,input().split())
v = {"U":0, "D":1, "L":2, "R":3}
g = gcd(w, h)
rl = [0] * 4 # 方向のカウント
x = [0] * m # X
y = [0] * m # Y
r = [0] * m # 方向
# 入力
for i in range(m):
xs, ys, d = input().split()
x[i] = int(xs)
y[i] = int(ys)
r[i] = v[d]
rl[r[i]] += 1
ans = 0
ans += count_type1(m, rl, x, y, r, w, h, g)
ans += count_type2(m, rl, x, y, r, w, h, g)
ans += count_type3(m, rl, x, y, r, w, h, g)
ans += count_type4(m, rl, x, y, r, w, h, g)
ans += count_type451(m, rl, x, y, r, w, h, g)
ans += count_type452(m, rl, x, y, r, w, h, g)
ans += count_type5(m, rl, x, y, r, w, h, g)
ans %= mod
return ans
T = int(input())
for _ in range(T):
print(solve())