結果
問題 | No.147 試験監督(2) |
ユーザー | Mao-beta |
提出日時 | 2024-03-19 10:46:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,421 ms / 2,000 ms |
コード長 | 1,848 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,500 KB |
実行使用メモリ | 91,136 KB |
最終ジャッジ日時 | 2024-09-30 05:17:39 |
合計ジャッジ時間 | 6,879 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,421 ms
91,136 KB |
testcase_01 | AC | 1,405 ms
91,136 KB |
testcase_02 | AC | 1,392 ms
91,008 KB |
testcase_03 | AC | 56 ms
65,024 KB |
ソースコード
import sys import math import bisect from heapq import heapify, heappop, heappush from collections import deque, defaultdict, Counter from functools import lru_cache from itertools import accumulate, combinations, permutations, product sys.setrecursionlimit(1000000) MOD = 10 ** 9 + 7 MOD99 = 998244353 input = lambda: sys.stdin.readline().strip() NI = lambda: int(input()) NMI = lambda: map(int, input().split()) NLI = lambda: list(NMI()) SI = lambda: input() SMI = lambda: input().split() SLI = lambda: list(SMI()) EI = lambda m: [NLI() for _ in range(m)] # 行列積(任意サイズ) def mul_matrix(A, B, mod=998244353): Ah = len(A) Aw = len(A[0]) Bh = len(B) Bw = len(B[0]) assert Aw == Bh C = [[0] * Bw for _ in range(Ah)] for h in range(Ah): Arow = A[h] Crow = C[h] for i in range(Aw): a = Arow[i] Brow = B[i] for w in range(Bw): Crow[w] = (Crow[w] + a * Brow[w]) % mod return C # 正方行列の累乗 mod def pow_matrix(A, n, mod=998244353): assert len(A) == len(A[0]) bitn = len(bin(n)) - 2 pows = [] size = len(A) E = [[0] * size for _ in range(size)] for i in range(size): E[i][i] = 1 pows.append(A) ans = E for i in range(bitn): if (n >> i) & 1: ans = mul_matrix(pows[-1], ans, mod) pows.append(mul_matrix(pows[-1], pows[-1], mod)) return ans def main(): N = NI() CD = EI(N) # z 1 1 y # y 1 0 x A = [[1, 1], [1, 0]] x = [2, 1] ans = 1 for c, d in CD: F = pow_matrix(A, c-1, MOD) t = (F[0][0] * x[0] + F[0][1] * x[1]) % MOD if t == 0: print(0) return ans = ans * pow(t, d%(MOD-1), MOD) % MOD print(ans) if __name__ == "__main__": main()