結果
問題 | No.2435 Order All Company |
ユーザー |
![]() |
提出日時 | 2023-09-18 17:33:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 1,386 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 82,432 KB |
最終ジャッジ日時 | 2024-07-05 07:39:05 |
合計ジャッジ時間 | 5,220 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
import sysinput = sys.stdin.readlineN, K = map(int, input().split())mod = 998244353Edge = [[] for i in range(K)]for i in range(K):t = int(input())for _ in range(t):a, b = map(int, input().split())a, b = a - 1, b - 1Edge[i].append((a, b))def determinant(A, mod):ans = 1N = len(A) - 1for i in range(N):if A[i][i] == 0:for j in range(i + 1, N):if A[j][i] != 0:A[i], A[j] = A[j], A[i]ans *= -1breakelse:return 0ans *= A[i][i]ans %= modinv = pow(A[i][i], mod - 2, mod)for j in range(i, N):A[i][j] *= invA[i][j] %= modfor j in range(i + 1, N):x = A[j][i]for k in range(i, N):A[j][k] -= x * A[i][k]A[j][k] %= modreturn ansK2 = 1 << Kans = 0for s in range(1, K2):pm = (-1) ** KL = [[0] * N for i in range(N)]for i in range(K):if (s >> i) & 1:pm *= -1for a, b in Edge[i]:L[a][a] += 1L[b][b] += 1L[a][b] -= 1L[b][a] -= 1ans += determinant(L, mod) * pmans %= modprint(ans)