結果

問題 No.3105 Parallel Connection and Spanning Trees
コンテスト
ユーザー PNJ
提出日時 2025-04-11 21:53:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,423 ms / 5,000 ms
コード長 1,662 bytes
コンパイル時間 494 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 82,220 KB
最終ジャッジ日時 2025-04-11 21:54:19
合計ジャッジ時間 18,497 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 998244353

def matrix_determinant(A, mod = 998244353):
  n = len(A)
  B = [[A[i][j] for j in range(n)] for i in range(n)]
  res = 1
  for i in range(n):
    if B[i][i] == 0:
      for j in range(i + 1, n):
        if B[i][j] != 0:
          for k in range(i, n):
            B[i][k], B[j][k] = B[j][k], B[i][k]
          res = mod - res
          break
      if B[i][i] == 0:
        return 0
    a = B[i][i]
    res = res * a % mod
    a_inv = pow(a, -1, mod)
    for j in range(i, n):
      B[i][j] = B[i][j] * a_inv % mod
    for j in range(i + 1, n):
      a = B[j][i]
      for k in range(i, n):
        B[j][k] = (B[j][k] - B[i][k] * a) % mod
  return res

def count_spanning_tree(G, r = 0, mod = 998244353):
  N = len(G)
  A = [[0 for j in range(N - 1)] for i in range(N - 1)]
  for u in range(N):
    i = u - int(u > r)
    for v in range(N):
      if v == r:
        continue
      j = v - int(v > r)
      A[j][j] += G[u][v]
      if u != r:
        A[j][i] -= G[u][v]
  return matrix_determinant(A, mod)

K = int(input())
C = [0 for _ in range(K)]
CC = [0 for _ in range(K)]
for i in range(K):
  N, M = map(int, input().split())
  G = [[0 for _ in range(N)] for _ in range(N)]
  GG = [[0 for _ in range(N)] for _ in range(N)]
  for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    G[A][B] += 1
    G[B][A] += 1
    GG[A][B] += 1
    GG[B][A] += 1
  GG[0][1] += 1
  GG[1][0] += 1
  C[i] = count_spanning_tree(G)
  CC[i] = (count_spanning_tree(GG) - C[i]) % mod

ans = 0
for k in range(K):
  c = C[k]
  for i in range(K):
    if i == k: continue
    c = c * (2 * C[i] + CC[i]) % mod
  ans = (ans + c) % mod
print(ans)
0