結果
問題 | No.2837 Flip Triomino |
ユーザー | detteiuu |
提出日時 | 2024-08-09 23:48:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 337 ms / 2,000 ms |
コード長 | 1,464 bytes |
コンパイル時間 | 453 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 122,524 KB |
最終ジャッジ日時 | 2024-08-09 23:49:03 |
合計ジャッジ時間 | 9,443 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
52,224 KB |
testcase_01 | AC | 33 ms
52,096 KB |
testcase_02 | AC | 37 ms
52,736 KB |
testcase_03 | AC | 33 ms
52,096 KB |
testcase_04 | AC | 35 ms
52,608 KB |
testcase_05 | AC | 35 ms
52,352 KB |
testcase_06 | AC | 37 ms
52,480 KB |
testcase_07 | AC | 335 ms
121,600 KB |
testcase_08 | AC | 335 ms
122,088 KB |
testcase_09 | AC | 324 ms
121,216 KB |
testcase_10 | AC | 323 ms
121,656 KB |
testcase_11 | AC | 324 ms
121,464 KB |
testcase_12 | AC | 278 ms
112,256 KB |
testcase_13 | AC | 239 ms
104,436 KB |
testcase_14 | AC | 265 ms
111,616 KB |
testcase_15 | AC | 301 ms
112,256 KB |
testcase_16 | AC | 292 ms
113,152 KB |
testcase_17 | AC | 308 ms
116,520 KB |
testcase_18 | AC | 279 ms
111,880 KB |
testcase_19 | AC | 300 ms
116,224 KB |
testcase_20 | AC | 265 ms
111,744 KB |
testcase_21 | AC | 247 ms
107,520 KB |
testcase_22 | AC | 332 ms
122,524 KB |
testcase_23 | AC | 337 ms
122,180 KB |
testcase_24 | AC | 335 ms
122,368 KB |
testcase_25 | AC | 330 ms
121,836 KB |
testcase_26 | AC | 330 ms
121,364 KB |
testcase_27 | AC | 156 ms
85,120 KB |
testcase_28 | AC | 76 ms
70,016 KB |
testcase_29 | AC | 86 ms
71,552 KB |
testcase_30 | AC | 151 ms
85,352 KB |
testcase_31 | AC | 163 ms
86,144 KB |
testcase_32 | AC | 127 ms
84,832 KB |
testcase_33 | AC | 248 ms
107,392 KB |
testcase_34 | AC | 40 ms
52,992 KB |
testcase_35 | AC | 61 ms
64,000 KB |
testcase_36 | AC | 198 ms
89,344 KB |
ソースコード
class CP: def __init__(self, N): self.fact = [1] self.fact_inv = [1] for i in range(1, N+1): self.fact.append((self.fact[-1]*i)%MOD) self.fact_inv.append(pow(self.fact[-1], MOD-2, MOD)) def C(self, N, K): if N >= K: return self.fact[N]*self.fact_inv[K]%MOD*self.fact_inv[N-K]%MOD else: return 0 def P(self, N, K): if N >= K: return self.fact[N]*self.fact_inv[N-K]%MOD else: return 0 N, M = map(int, input().split()) S = [list(input()) for _ in range(N)] cnt = [0]*3 Q = [0]*3 MOD = 998244353 for i in range(N): for j in range(M): if S[i][j] == "B": cnt[(i+j)%3] += 1 elif S[i][j] == "?": Q[(i+j)%3] += 1 cp = CP(N*M) odd = 1 for i in range(3): o = 0 if cnt[i]%2 == 0: c = 1 while c <= Q[i]: o += cp.C(Q[i], c) o %= MOD c += 2 else: c = 0 while c <= Q[i]: o += cp.C(Q[i], c) o %= MOD c += 2 odd *= o odd %= MOD even = 1 for i in range(3): e = 0 if cnt[i]%2 == 0: c = 0 while c <= Q[i]: e += cp.C(Q[i], c) e %= MOD c += 2 else: c = 1 while c <= Q[i]: e += cp.C(Q[i], c) e %= MOD c += 2 even *= e even %= MOD print((odd+even)%MOD)