結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
![]() |
提出日時 | 2021-11-19 21:43:10 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 566 bytes |
コンパイル時間 | 344 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 79,776 KB |
最終ジャッジ日時 | 2024-12-31 22:30:28 |
合計ジャッジ時間 | 39,285 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 TLE * 3 |
ソースコード
import numpy as np MOD = 998244353 def mult(N, A, B): C = np.zeros((N, N), np.int64) for n in range(N): C[n] = (A[n, :][:, None] * B % MOD).sum(axis=0) % MOD return C def mat_power(A, N, k): if k == 0: return np.eye(N, dtype=np.int64) X = mat_power(A, N, k//2) X = mult(N, X, X) return mult(N, A, X) if k & 1 else X n, m, tt = map(int, input().split()) a = np.zeros((n, n), np.int64) for i in range(m): s, t = map(int, input().split()) a[s][t] = 1 a[t][s] = 1 print(mat_power(a, n, tt)[0][0] % MOD)