結果
問題 |
No.2711 Connecting Lights
|
ユーザー |
![]() |
提出日時 | 2024-06-22 14:04:30 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,269 bytes |
コンパイル時間 | 255 ms |
コンパイル使用メモリ | 82,332 KB |
実行使用メモリ | 67,012 KB |
最終ジャッジ日時 | 2024-06-22 14:04:34 |
合計ジャッジ時間 | 2,796 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 WA * 2 |
ソースコード
def full(shape, fill_value): if len(shape) == 1: return [fill_value] * shape[0] return [full(shape[1:], fill_value) for _ in range(shape[0])] def vector(seq: list[int]|tuple[int, ...]): return [[x] for x in seq] def matmul(A, B, MOD): X = len(A) Y = len(A[0]) assert Y == len(B) Z = len(B[0]) tB = [[B[j][k] for j in range(Y)] for k in range(Z)] res = [] for i in range(X): nrow = [0]*Z Ai = A[i] for k in range(Z): tBk = tB[k] for j in range(Y): term = Ai[j] * tBk[j] nrow[k] += term nrow[k] %= MOD res.append(nrow) return res def matpow(base, exp, MOD): assert len(base) == len(base[0]) N = len(base) res = [[int(i == j) for j in range(N)] for i in range(N)] while exp: if exp&1: res = matmul(res, base, MOD) base = matmul(base, base, MOD) exp >>= 1 return res MOD = 998_244_353 N, M, K = map(int, input().split()) mat = full((1<<N, 1<<N), 0) for S in range(1<<N): for nS in range(1<<N): if int.bit_count(S&nS) < K: continue mat[nS][S] += 1 V = vector([0]*((1<<N) - 1) + [1]) mat = matpow(mat, M, MOD) V = matmul(mat, V, MOD) ans = sum(row[0] for row in V) ans %= MOD print(ans)