結果

問題 No.2435 Order All Company
ユーザー LyricalMaestro
提出日時 2024-01-23 02:57:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 233 ms / 2,000 ms
コード長 3,348 bytes
コンパイル時間 272 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 78,080 KB
最終ジャッジ日時 2024-09-28 06:34:42
合計ジャッジ時間 6,785 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

## 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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0