結果
問題 | No.147 試験監督(2) |
ユーザー | commy |
提出日時 | 2020-05-01 01:40:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,032 ms / 2,000 ms |
コード長 | 711 bytes |
コンパイル時間 | 628 ms |
コンパイル使用メモリ | 82,328 KB |
実行使用メモリ | 78,512 KB |
最終ジャッジ日時 | 2024-06-01 06:19:58 |
合計ジャッジ時間 | 6,264 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,007 ms
78,420 KB |
testcase_01 | AC | 1,027 ms
78,284 KB |
testcase_02 | AC | 1,032 ms
78,512 KB |
testcase_03 | AC | 54 ms
63,100 KB |
ソースコード
n = int(input()) mod = 1000000007 def matrixmul(a, b): res = [0, 0, 0, 0] for i in range(2): for j in range(2): for k in range(2): res[2 * i + j] += a[2 * i + k] * b[2 * k + j] res[2 * i + j] %= mod return res def powmatrix(matrix, p): ans = [1, 0, 0, 1] while p > 0: if p % 2 == 1: ans = matrixmul(ans, matrix) matrix = matrixmul(matrix, matrix) p >>= 1 return ans matrix = [1, 1, 1, 0] ans = 1 for i in range(n): c, d = map(int, input().split()) res = powmatrix(matrix, c + 1)[0] d %= (mod - 1) if d == 0: d = mod - 1 ans *= pow(res, d, mod) ans %= mod print(ans)