結果
問題 | No.891 隣接3項間の漸化式 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:05:45 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 532 ms / 2,000 ms |
コード長 | 709 bytes |
コンパイル時間 | 133 ms |
コンパイル使用メモリ | 12,416 KB |
実行使用メモリ | 44,428 KB |
最終ジャッジ日時 | 2024-09-14 17:41:37 |
合計ジャッジ時間 | 25,351 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
#!/usr/bin/env python3import numpyM = 10 ** 9 + 7def mat_mul_mod(x, y, mod=M):return x @ y % moddef mat_pow_mod(x, n, mod=M):y = numpy.array([[1, 0], [0, 1]], dtype=numpy.int64)while n > 0:if n % 2 == 1:y = mat_mul_mod(y, x, mod)x = mat_mul_mod(x, x, mod)n >>= 1return ydef solve(a, b, n, mod=M):x = numpy.array([[a, b], [1, 0]], dtype=numpy.int64)res = mat_pow_mod(x, n)z = numpy.array([[1, ], [0, ]], dtype=numpy.int64)res = mat_mul_mod(res, z, mod)return res[1, 0]def main():a, b, n = (int(z) for z in input().split())ans = solve(a, b, n)print(ans)if __name__ == "__main__":main()