結果
問題 | No.2435 Order All Company |
ユーザー | LyricalMaestro |
提出日時 | 2024-01-23 02:57:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 251 ms / 2,000 ms |
コード長 | 3,348 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 77,840 KB |
最終ジャッジ日時 | 2024-01-23 02:57:35 |
合計ジャッジ時間 | 8,137 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,460 KB |
testcase_01 | AC | 37 ms
53,460 KB |
testcase_02 | AC | 36 ms
53,460 KB |
testcase_03 | AC | 36 ms
53,460 KB |
testcase_04 | AC | 51 ms
64,208 KB |
testcase_05 | AC | 230 ms
77,708 KB |
testcase_06 | AC | 233 ms
77,840 KB |
testcase_07 | AC | 184 ms
77,580 KB |
testcase_08 | AC | 223 ms
77,584 KB |
testcase_09 | AC | 251 ms
77,708 KB |
testcase_10 | AC | 74 ms
73,080 KB |
testcase_11 | AC | 55 ms
66,288 KB |
testcase_12 | AC | 51 ms
64,064 KB |
testcase_13 | AC | 59 ms
68,204 KB |
testcase_14 | AC | 184 ms
77,068 KB |
testcase_15 | AC | 184 ms
77,204 KB |
testcase_16 | AC | 156 ms
76,428 KB |
testcase_17 | AC | 234 ms
77,840 KB |
testcase_18 | AC | 164 ms
77,072 KB |
testcase_19 | AC | 137 ms
76,304 KB |
testcase_20 | AC | 139 ms
75,916 KB |
testcase_21 | AC | 157 ms
76,684 KB |
testcase_22 | AC | 182 ms
77,324 KB |
testcase_23 | AC | 128 ms
76,300 KB |
testcase_24 | AC | 203 ms
77,456 KB |
testcase_25 | AC | 171 ms
77,068 KB |
testcase_26 | AC | 174 ms
77,324 KB |
testcase_27 | AC | 170 ms
77,068 KB |
testcase_28 | AC | 132 ms
75,916 KB |
testcase_29 | AC | 177 ms
77,196 KB |
testcase_30 | AC | 200 ms
77,200 KB |
testcase_31 | AC | 38 ms
53,460 KB |
testcase_32 | AC | 36 ms
53,460 KB |
testcase_33 | AC | 36 ms
53,460 KB |
testcase_34 | AC | 72 ms
73,072 KB |
testcase_35 | AC | 111 ms
76,720 KB |
ソースコード
## https://yukicoder.me/problems/no/2435 MOD = 998244353 def main(): N, K = map(int, input().split()) edges = [] for _ in range(K): edges_map = {} t = int(input()) for _ in range(t): a, b = map(int, input().split()) a_ = min(a, b) - 1 b_ = max(a, b) - 1 if (a_, b_) not in edges_map: edges_map[(a_, b_)] = 0 edges_map[(a_, b_)] += 1 edges.append(edges_map) values_bit_map = {} for bit in range(1, 1 << K): edges_map = {} for i in range(K): if bit & (1 << i): for k, v in edges[i].items(): if k not in edges_map: edges_map[k] = 0 edges_map[k] += v # 行列木定理を用いる tree_matrix = [[0] * N for _ in range(N)] for (a, b), v in edges_map.items(): tree_matrix[a][a] += v tree_matrix[a][a] %= MOD tree_matrix[b][b] += v tree_matrix[b][b] %= MOD tree_matrix[a][b] -= v tree_matrix[a][b] %= MOD tree_matrix[b][a] -= v tree_matrix[b][a] %= MOD tree_adj_matrix = [[0] * (N - 1) for _ in range(N - 1)] for i in range(N - 1): for j in range(N - 1): tree_adj_matrix[i][j] = tree_matrix[i + 1][j + 1] # 上三角行列に変形 coef = 1 det = 0 is_ok = True for i in range(N - 1): if tree_adj_matrix[i][i] == 0: is_ok = False for j in range(i + 1, N - 1): if tree_adj_matrix[j][i] != 0: for k in range(N - 1): tmp = tree_adj_matrix[i][k] tree_adj_matrix[i][k] = tree_adj_matrix[j][k] tree_adj_matrix[j][k] = tmp coef *= pow(-1, j - i, MOD) is_ok = True break if not is_ok: break # 体格成分を1にする a = pow(tree_adj_matrix[i][i], MOD - 2, MOD) coef *= tree_adj_matrix[i][i] coef %= MOD for k in range(N - 1): tree_adj_matrix[i][k] *= a tree_adj_matrix[i][k] %= MOD for j in range(i + 1, N - 1): a = tree_adj_matrix[j][i] for k in range(i, N - 1): tree_adj_matrix[j][k] -= (a * tree_adj_matrix[i][k]) % MOD tree_adj_matrix[j][k] %= MOD if is_ok: det = 1 for i in range(N - 1): det *= tree_adj_matrix[i][i] det %= MOD det *= coef det %= MOD values_bit_map[bit] = det answer = 0 for bit in range(1, 1 << K): count = 0 for i in range(K): if bit & (1 << i) == 0: count += 1 coef = 1 if count > 0: coef = pow(-1, count, MOD) answer += (coef * values_bit_map[bit]) % MOD answer %= MOD print(answer) if __name__ == '__main__': main()