結果
問題 |
No.1750 ラムドスウイルスの感染拡大-hard
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:54:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,900 ms / 2,000 ms |
コード長 | 1,617 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 82,656 KB |
実行使用メモリ | 104,576 KB |
最終ジャッジ日時 | 2025-03-20 18:56:20 |
合計ジャッジ時間 | 18,913 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
MOD = 998244353 def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]); idx +=1 M = int(data[idx]); idx +=1 T = int(data[idx]); idx +=1 # Initialize adjacency matrix adj = [[0]*N for _ in range(N)] for _ in range(M): s = int(data[idx]); idx +=1 t = int(data[idx]); idx +=1 adj[s][t] += 1 adj[t][s] += 1 # Function to multiply two matrices with optimization def multiply(a, b): n = len(a) result = [[0]*n for _ in range(n)] bt = list(zip(*b)) # Transpose b for i in range(n): a_row = a[i] for j in range(n): total = 0 b_col = bt[j] for k in range(n): total += a_row[k] * b_col[k] result[i][j] = total % MOD return result # Function to compute matrix exponentiation using binary exponentiation def matrix_power(mat, power): n = len(mat) result = [[0]*n for _ in range(n)] for i in range(n): result[i][i] = 1 # Identity matrix current = mat while power > 0: if power % 2 == 1: result = multiply(result, current) current = multiply(current, current) power = power // 2 return result if T == 0: print(1 % MOD) return # Compute A^T mat_T = matrix_power(adj, T) # The result is the (0,0) entry of mat_T print(mat_T[0][0] % MOD) if __name__ == "__main__": main()