結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー |
|
提出日時 | 2021-11-19 22:34:37 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,088 ms / 2,000 ms |
コード長 | 1,145 bytes |
コンパイル時間 | 421 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 77,276 KB |
最終ジャッジ日時 | 2025-01-01 19:29:31 |
合計ジャッジ時間 | 13,852 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
import sysinput = sys.stdin.readlinedef iinput(): return int(input())def sinput(): return input().rstrip()def i0input(): return int(input()) - 1def linput(): return list(input().split())def liinput(): return list(map(int, input().split()))def miinput(): return map(int, input().split())def li0input(): return list(map(lambda x: int(x) - 1, input().split()))def mi0input(): return map(lambda x: int(x) - 1, input().split())INF = 10**20MOD = 998244353def mat_mul(a, b) :I, J, K = len(a), len(b[0]), len(b)c = [[0] * J for _ in range(I)]for i in range(I) :for j in range(J) :for k in range(K) :c[i][j] += a[i][k] * b[k][j]c[i][j] %= MODreturn cdef mat_pow(x, n):y = [[0] * len(x) for _ in range(len(x))]for i in range(len(x)):y[i][i] = 1while n > 0:if n & 1:y = mat_mul(x, y)x = mat_mul(x, x)n >>= 1return yN, M, T = liinput()g = [[0 for _ in range(N)] for _ in range(N)]for _ in [0] * M:s, t = liinput()g[s][t] = 1g[t][s] = 1ans = mat_pow(g, T)print(ans[0][0])