結果
問題 |
No.2711 Connecting Lights
|
ユーザー |
|
提出日時 | 2024-04-07 14:26:40 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 834 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 82,128 KB |
実行使用メモリ | 65,832 KB |
最終ジャッジ日時 | 2024-10-01 04:29:40 |
合計ジャッジ時間 | 2,540 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 WA * 2 |
ソースコード
MOD = 998244353 def mat_exp_global_mod(A, B, n): le = len(A) while n > 0: if n & 1: C = [0] * le for i in range(le): for j in range(le): C[i] += A[i][j] * B[j] C[i] %= MOD B = C C = [[0] * le for _ in range(le)] for i in range(le): for k in range(le): for j in range(le): C[i][j] += A[i][k] * A[k][j] C[i][j] %= MOD A = C n >>= 1 return B n, m, k = map(int, input().split()) x = 1 << n A = [[0] * x for _ in range(x)] for bit1 in range(x): for bit2 in range(x): if bin(bit1 & bit2).count("1") >= k: A[bit1][bit2] = 1 B = [0] * x B[-1] = 1 C = mat_exp_global_mod(A, B, m) print(sum(C) % MOD)