結果
| 問題 |
No.2257 Swim and Sleep
|
| コンテスト | |
| ユーザー |
 shobonvip
|
| 提出日時 | 2023-03-24 06:32:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 436 ms / 2,000 ms |
| コード長 | 6,752 bytes |
| コンパイル時間 | 242 ms |
| コンパイル使用メモリ | 82,128 KB |
| 実行使用メモリ | 80,840 KB |
| 最終ジャッジ日時 | 2024-09-18 15:53:07 |
| 合計ジャッジ時間 | 6,320 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 17 |
ソースコード
# コードを綺麗にした
from math import gcd
from collections import defaultdict
mod = 998244353
# m ... 決まっている鯨の数
# rl ... 方向の個数 (長さ 4 の配列)
# x ... 鯨の x 座標 (長さ m の配列)
# y ... 鯨の y 座標 (長さ m の配列)
# r ... 鯨の方向 (長さ m の配列)
# w ... 盤面の x 軸の広さ
# h ... 盤面の y 軸の広さ
# g ... gcd(w, h)
# 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(lambda:-1)
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(lambda:-1)
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
# TYPE 3, 4 のうち, TYPE 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
# TYPE 3, 4 のうち, TYPE 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
# 非自明の 48 通りを作る
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
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
# 衝突しなかった場合, TYPE 1, 2, 3, 4 に当てはまるかを確認
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)
# TYPE 1, 2, 3, 4 に当てはまらない場合, 非自明
if ans == 0:
ret.append(a)
return ret
# 実行！
ar = make_hijimei()
# TYPE 5
# 非自明 48通りを全探索する
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())