結果
問題 | No.2435 Order All Company |
ユーザー |
|
提出日時 | 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 |
ソースコード
## https://yukicoder.me/problems/no/2435MOD = 998244353def 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) - 1b_ = max(a, b) - 1if (a_, b_) not in edges_map:edges_map[(a_, b_)] = 0edges_map[(a_, b_)] += 1edges.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] = 0edges_map[k] += v# 行列木定理を用いるtree_matrix = [[0] * N for _ in range(N)]for (a, b), v in edges_map.items():tree_matrix[a][a] += vtree_matrix[a][a] %= MODtree_matrix[b][b] += vtree_matrix[b][b] %= MODtree_matrix[a][b] -= vtree_matrix[a][b] %= MODtree_matrix[b][a] -= vtree_matrix[b][a] %= MODtree_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 = 1det = 0is_ok = Truefor i in range(N - 1):if tree_adj_matrix[i][i] == 0:is_ok = Falsefor 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] = tmpcoef *= pow(-1, j - i, MOD)is_ok = Truebreakif not is_ok:break# 体格成分を1にするa = pow(tree_adj_matrix[i][i], MOD - 2, MOD)coef *= tree_adj_matrix[i][i]coef %= MODfor k in range(N - 1):tree_adj_matrix[i][k] *= atree_adj_matrix[i][k] %= MODfor 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]) % MODtree_adj_matrix[j][k] %= MODif is_ok:det = 1for i in range(N - 1):det *= tree_adj_matrix[i][i]det %= MODdet *= coefdet %= MODvalues_bit_map[bit] = detanswer = 0for bit in range(1, 1 << K):count = 0for i in range(K):if bit & (1 << i) == 0:count += 1coef = 1if count > 0:coef = pow(-1, count, MOD)answer += (coef * values_bit_map[bit]) % MODanswer %= MODprint(answer)if __name__ == '__main__':main()