結果
問題 | No.1750 ラムドスウイルスの感染拡大-hard |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-14 17:49:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,852 ms / 2,000 ms |
コード長 | 2,810 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 81,516 KB |
実行使用メモリ | 78,348 KB |
最終ジャッジ日時 | 2023-10-18 11:56:59 |
合計ジャッジ時間 | 22,174 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 64 ms
67,952 KB |
testcase_01 | AC | 64 ms
67,952 KB |
testcase_02 | AC | 67 ms
68,420 KB |
testcase_03 | AC | 72 ms
70,696 KB |
testcase_04 | AC | 131 ms
77,420 KB |
testcase_05 | AC | 65 ms
67,972 KB |
testcase_06 | AC | 64 ms
67,972 KB |
testcase_07 | AC | 65 ms
67,972 KB |
testcase_08 | AC | 389 ms
77,704 KB |
testcase_09 | AC | 387 ms
77,704 KB |
testcase_10 | AC | 387 ms
77,704 KB |
testcase_11 | AC | 319 ms
77,712 KB |
testcase_12 | AC | 412 ms
77,712 KB |
testcase_13 | AC | 392 ms
77,716 KB |
testcase_14 | AC | 1,709 ms
78,340 KB |
testcase_15 | AC | 1,748 ms
78,348 KB |
testcase_16 | AC | 1,767 ms
78,344 KB |
testcase_17 | AC | 1,800 ms
78,336 KB |
testcase_18 | AC | 1,852 ms
78,332 KB |
testcase_19 | AC | 1,782 ms
78,336 KB |
testcase_20 | AC | 1,256 ms
77,884 KB |
testcase_21 | AC | 1,464 ms
77,980 KB |
testcase_22 | AC | 324 ms
77,388 KB |
testcase_23 | AC | 1,692 ms
78,260 KB |
testcase_24 | AC | 264 ms
77,400 KB |
testcase_25 | AC | 530 ms
77,468 KB |
testcase_26 | AC | 222 ms
77,380 KB |
testcase_27 | AC | 75 ms
73,148 KB |
testcase_28 | AC | 92 ms
77,324 KB |
testcase_29 | AC | 75 ms
72,932 KB |
testcase_30 | AC | 319 ms
77,412 KB |
testcase_31 | AC | 304 ms
77,416 KB |
testcase_32 | AC | 298 ms
77,416 KB |
testcase_33 | AC | 298 ms
77,412 KB |
ソースコード
from typing import List M = List[List[int]] class MatPow: __slots__ = ("_n", "_mod", "_base", "_cacheLevel", "_useCache", "_cache") def __init__(self, base: M, mod=1000000007, cacheLevel=4): n = len(base) b = [0] * n * n for i in range(n): for j in range(n): b[i * n + j] = base[i][j] useCache = cacheLevel >= 2 self._n = n self._mod = mod self._base = b self._cacheLevel = cacheLevel self._useCache = useCache if useCache: self._cache = [[] for _ in range(cacheLevel - 1)] def pow(self, exp: int) -> M: if not self._useCache: return self._powWithOutCache(exp) if len(self._cache[0]) == 0: self._cache[0].append(self._base) for i in range(1, self._cacheLevel - 1): self._cache[i].append(self._mul(self._cache[i - 1][0], self._base)) e = self._eye(self._n) div = 0 while exp: if div == len(self._cache[0]): self._cache[0].append( self._mul(self._cache[self._cacheLevel - 2][div - 1], self._cache[0][div - 1]) ) for i in range(1, self._cacheLevel - 1): self._cache[i].append(self._mul(self._cache[i - 1][div], self._cache[0][div])) mod = exp % self._cacheLevel if mod: e = self._mul(e, self._cache[mod - 1][div]) exp //= self._cacheLevel div += 1 return self._to2D(e) def _mul(self, mat1: List[int], mat2: List[int]) -> List[int]: n = self._n res = [0] * n * n for i in range(n): for k in range(n): for j in range(n): res[i * n + j] = ( res[i * n + j] + mat1[i * n + k] * mat2[k * n + j] ) % self._mod return res def _powWithOutCache(self, exp: int) -> M: e = self._eye(self._n) b = self._base[:] while exp: if exp & 1: e = self._mul(e, b) exp >>= 1 b = self._mul(b, b) return self._to2D(e) def _eye(self, n: int) -> List[int]: res = [0] * n * n for i in range(n): res[i * n + i] = 1 return res def _to2D(self, mat: List[int]) -> M: n = self._n return [mat[i * n : (i + 1) * n] for i in range(n)] def __pow__(self, exp: int) -> M: return self.pow(exp) n, m, k = map(int, input().split()) adjMatrix = [[0] * n for _ in range(n)] for _ in range(m): u, v = map(int, input().split()) adjMatrix[u][v] = 1 adjMatrix[v][u] = 1 P = MatPow(adjMatrix, 998244353, cacheLevel=-1) res = P.pow(k)[0][0] print(res)