結果

問題 No.3105 Parallel Connection and Spanning Trees
ユーザー shobonvip
提出日時 2025-01-18 05:32:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,978 ms / 5,000 ms
コード長 1,332 bytes
コンパイル時間 1,110 ms
コンパイル使用メモリ 81,552 KB
実行使用メモリ 79,888 KB
最終ジャッジ日時 2025-01-28 22:58:22
合計ジャッジ時間 24,180 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

def det(M, mod):
	M = [row[:] for row in M]
	N, sign, prev = len(M), 1, 1
	for i in range(N-1):
		if M[i][i] == 0:
			swapto = next((j for j in range(i+1, N) if M[j][i] != 0), None)
			if swapto is None:
				return 0
			M[i], M[swapto], sign = M[swapto], M[i], -sign
		previnv = pow(prev, mod-2, mod)
		for j in range(i+1, N):
			for k in range(i+1, N):
				M[j][k] = (M[j][k]*M[i][i]%mod-M[j][i]*M[i][k]%mod)*previnv%mod
		prev = M[i][i]
	return sign*M[-1][-1]%mod

k = int(input())
dp = [[0]*2 for i in range(k+1)]
dp[0][0] = 1
mod = 998244353

for i in range(k):
	n, m = map(int,input().split())
	mat1 = [[0]*(n-1) for j in range(n-1)]
	for j in range(m):
		x, y = map(int,input().split())
		x -= 1
		y -= 1
		if x-1 >= 0 and y-1 >= 0:
			mat1[x-1][y-1] -= 1
			mat1[x-1][y-1] %= mod
			mat1[y-1][x-1] -= 1
			mat1[y-1][x-1] %= mod
		if x-1 >= 0:
			mat1[x-1][x-1] += 1
			mat1[x-1][x-1] %= mod
		if y-1 >= 0:
			mat1[y-1][y-1] += 1
			mat1[y-1][y-1] %= mod
	mat2 = [mat1[j][::] for j in range(n-1)]
	mat2[0][0] += 1
	mat2[0][0] %= mod
	val1 = det(mat1, mod)
	val2 = det(mat2, mod)
	type123 = val1
	type4 = (val2 - val1) % mod
	dp[i+1][1] += dp[i][0] * type123 % mod
	dp[i+1][1] += dp[i][1] * (type123 * 2 + type4) % mod
	dp[i+1][0] += dp[i][0] * (type123 * 2 + type4) % mod
	dp[i+1][0] %= mod
	dp[i+1][1] %= mod

print(dp[k][1])
0