結果
問題 | No.147 試験監督(2) |
ユーザー | roaris |
提出日時 | 2019-12-04 21:06:17 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 870 bytes |
コンパイル時間 | 2,123 ms |
コンパイル使用メモリ | 87,032 KB |
実行使用メモリ | 86,772 KB |
最終ジャッジ日時 | 2023-08-21 02:19:39 |
合計ジャッジ時間 | 9,940 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | TLE | - |
testcase_01 | TLE | - |
testcase_02 | TLE | - |
testcase_03 | AC | 74 ms
71,344 KB |
ソースコード
def mat_mul(A, B): C = [[0]*len(B[0]) for _ in range(len(A))] for i in range(len(A)): for j in range(len(B[0])): for k in range(len(B)): C[i][j] += A[i][k]*B[k][j] C[i][j] %= MOD return C def mat_pow(A, n): res = [[0]*len(A) for _ in range(len(A))] for i in range(len(A)): res[i][i] = 1 while n: if n&1: res = mat_mul(res, A) n >>= 1 A = mat_mul(A, A) return res N = int(input()) MOD = 10**9+7 ans = 1 CD = [tuple(map(int, input().split())) for _ in range(N)] CD.sort(key=lambda k: k[0]) A = [[1, 0], [0, 1]] prev_C = 0 for Ci, Di in CD: A = mat_mul(A, mat_pow([[1, 1], [1, 0]], Ci-prev_C)) F = mat_mul(A, [[1], [1]])[0][0]%MOD ans *= pow(F, Di, MOD) ans %= MOD prev_C = Ci print(ans)