結果
問題 |
No.1084 積の積
|
ユーザー |
![]() |
提出日時 | 2022-05-31 00:42:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 367 ms / 2,000 ms |
コード長 | 1,387 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 97,792 KB |
最終ジャッジ日時 | 2024-09-21 00:57:32 |
合計ジャッジ時間 | 5,930 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
import sys import pypyjit import itertools import heapq import math from collections import deque, defaultdict import bisect input = sys.stdin.readline sys.setrecursionlimit(10 ** 6) pypyjit.set_param('max_unroll_recursion=-1') def index_lt(a, x): 'return largest index s.t. A[i] < x or -1 if it does not exist' return bisect.bisect_left(a, x) - 1 def index_le(a, x): 'return largest index s.t. A[i] <= x or -1 if it does not exist' return bisect.bisect_right(a, x) - 1 def index_gt(a, x): 'return smallest index s.t. A[i] > x or len(a) if it does not exist' return bisect.bisect_right(a, x) def index_ge(a, x): 'return smallest index s.t. A[i] >= x or len(a) if it does not exist' return bisect.bisect_left(a, x) N = int(input()) A = list(map(int, input().split())) MOD = 10 ** 9 + 7 if 0 in A: print(0) exit() S = [] l = 0 r = 0 acc = 1 while r < N: acc *= A[r] if acc >= 10 ** 9: S.append((l, r)) while acc >= 10 ** 9: acc //= A[l] l += 1 r += 1 S.append((l, N)) ans = 1 for l, r in S: for i in range(l, r): ans *= pow(A[i], (i - l + 1) * (r - i), MOD) ans %= MOD for (a, b), (c, d) in zip(S[:-1], S[1:]): l = max(a, c) r = min(b, d) for i in range(l, r): ans *= pow(pow(A[i], (i - l + 1) * (r - i), MOD), MOD - 2, MOD) ans %= MOD print(ans)