結果
問題 | No.2435 Order All Company |
ユーザー |
|
提出日時 | 2023-08-18 22:34:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 206 ms / 2,000 ms |
コード長 | 1,404 bytes |
コンパイル時間 | 484 ms |
コンパイル使用メモリ | 81,536 KB |
実行使用メモリ | 82,176 KB |
最終ジャッジ日時 | 2024-11-28 08:35:22 |
合計ジャッジ時間 | 5,932 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
import sysfrom itertools import permutationsfrom heapq import *input = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())mod = 998244353def det(G, mod):N = len(G)res = 1for i in range(N):for h in range(i, N):if G[h][i]:breakif i != h:G[i], G[h] = G[h][:], G[i][:]gii = G[i][i]res = res*gii%modgiiv = pow(gii, mod-2, mod)for w in range(i, N):G[i][w] = G[i][w]*giiv%modfor j in range(i+1, N):gji = G[j][i]if gji:for w in range(i, N):G[j][w] = (G[j][w]-gji*G[i][w])%modreturn resdef calc_tree(N,A):return det([A[i][:N-1] for i in range(N-1)],mod)N,K = mi()edge = [[] for i in range(K)]for i in range(K):t = int(input())for _ in range(t):a,b = mi()edge[i].append((a-1,b-1))ans = 0for S in range(1<<K):A = [[0]*N for i in range(N)]p = 0for i in range(K):if S>>i & 1 == 0:for a,b in edge[i]:A[a][a] += 1A[b][b] += 1A[a][b] -= 1A[b][a] -= 1else:p += 1if p & 1 == 0:ans += calc_tree(N,A)else:ans -= calc_tree(N,A)ans %= modprint(ans)