結果
問題 | No.2156 ぞい文字列 |
ユーザー |
|
提出日時 | 2022-12-12 16:58:18 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
RE
|
実行時間 | - |
コード長 | 778 bytes |
コンパイル時間 | 97 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 44,716 KB |
最終ジャッジ日時 | 2024-11-06 14:39:02 |
合計ジャッジ時間 | 12,965 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 RE * 1 |
other | WA * 8 RE * 8 |
ソースコード
from typing import Sequence import numpy as np def mat_mul(mat1: np.matrix, mat2: np.matrix, mod: int = None): ans = mat1 * mat2 return ans if mod is None else ans % mod def mat_pow(mat1: Sequence[Sequence[int]], n: int, mod: int = None) -> Sequence[Sequence[int]]: mat1 = np.matrix(mat1) ans = np.identity(len(mat1)) while n > 0: if n & 1: ans = mat_mul(ans, mat1) mat1 = mat_mul(mat1, mat1) n >>= 1 return ans def main(): N = int(input()) MOD = 998244353 fib_matrix = np.matrix([[1, 1], [1, 0]]) init = np.array(([1, 0], )).T fib_matrix_pow = mat_pow(fib_matrix, N, MOD) fib_N = np.dot(fib_matrix_pow, init) print(int(fib_N[0, 0] - 1) % MOD) if __name__ == "__main__": main()