結果
問題 | No.2156 ぞい文字列 |
ユーザー | ikoma |
提出日時 | 2022-12-09 23:05:11 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,624 bytes |
コンパイル時間 | 295 ms |
コンパイル使用メモリ | 87,040 KB |
実行使用メモリ | 75,976 KB |
最終ジャッジ日時 | 2023-08-05 00:57:03 |
合計ジャッジ時間 | 2,924 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 82 ms
75,876 KB |
testcase_01 | AC | 82 ms
75,900 KB |
testcase_02 | AC | 82 ms
75,916 KB |
testcase_03 | AC | 82 ms
75,880 KB |
testcase_04 | AC | 83 ms
75,848 KB |
testcase_05 | AC | 80 ms
75,976 KB |
testcase_06 | AC | 82 ms
75,664 KB |
testcase_07 | AC | 81 ms
75,896 KB |
testcase_08 | AC | 74 ms
71,360 KB |
testcase_09 | AC | 73 ms
71,500 KB |
testcase_10 | AC | 73 ms
71,156 KB |
testcase_11 | AC | 74 ms
71,324 KB |
testcase_12 | AC | 75 ms
71,456 KB |
testcase_13 | AC | 73 ms
71,612 KB |
testcase_14 | AC | 74 ms
71,260 KB |
testcase_15 | AC | 73 ms
71,504 KB |
testcase_16 | AC | 71 ms
71,328 KB |
testcase_17 | AC | 75 ms
71,120 KB |
testcase_18 | AC | 73 ms
71,456 KB |
testcase_19 | AC | 82 ms
75,920 KB |
ソースコード
N=int(input()) if N==2:exit(print(1)) MOD=998244353 class matrix_mod: def __init__(self, data, mod:int=MOD): self._mat = data._mat if isinstance(data, self.__class__) else data self.row = len(data) self.col = len(data[0]) self.mod = mod @staticmethod def copy_m(m:list): return [[c for c in r] for r in m] @staticmethod def _mul(m1:list, m2:list, mod:int): return [[sum([(z1*z2)%mod for (z1,z2) in zip(x1,y2)])%mod for y2 in zip(*m2)] for x1 in m1] def mul(self, m:"matrix_mod"): assert self.col==m.row assert self.mod==m.mod return self.__class__(self.__class__._mul(self._mat, m._mat, self.mod), mod=self.mod) def __matmul__(self, other:"matrix_mod"): return self.mul(other) @classmethod def _pow(cls, m:list, n:int, mod:int): assert isinstance(n, int) assert n > 0 ret = None mm = cls.copy_m(m) while n: if n&1: if ret is None: ret = cls.copy_m(mm) else: ret = cls._mul(mm, ret, mod) mm = cls._mul(mm, mm, mod) n >>= 1 return ret def pow(self, n:int): assert self.row==self.col return self.__class__(self.__class__._pow(self._mat, n, self.mod), mod=self.mod) def __pow__(self, other:"matrix_mod"): print(other) return self.pow(other) m = matrix_mod([[1,1,0],[1,0,1],[0,0,1]], mod=MOD) m = m.pow(N-2) m2 = matrix_mod([[0],[1],[1]], mod=MOD) ans = matrix_mod([[1,1,0]], mod=MOD)@m @ m2 print(ans._mat[0][0])