結果
問題 | No.1084 積の積 |
ユーザー |
|
提出日時 | 2020-06-19 23:02:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 1,312 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 82,660 KB |
実行使用メモリ | 90,568 KB |
最終ジャッジ日時 | 2024-07-03 15:29:29 |
合計ジャッジ時間 | 3,333 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
N = int(input())A = list(map(int, input().split()))# left_mul = [0] * 100010# right_mul = [0] * 100010# left_mul[0] = 1# for i in range(N):# left_mul[i+1] = left_mul[i] * A[i]# right_mul[0] = 1# for i in range(N):# right_mul[i+1] = right_mul[i] * A[N-1-i]l1 = 0r1 = 1cur = A[0]ps = [0] * 100010for i in range(N):ps[i] = N-1while l1 < N:if r1 == N:ps[l1] = r1-1breakif cur * A[r1] >= 1000000000:ps[l1] = r1-1cur //= A[l1]l1 += 1else:cur *= A[r1]r1 += 1ans = 1MOD = 1000000007arr = [0] * 100010val = [0] * 100010for i in range(N):lv = ps[i]# rv = N# while rv - lv > 1:# mid = (rv + lv) // 2# mul_v = mul_all // left_mul[i] // right_mul[N-1-mid]# if mul_v >= 1000000000:# rv = mid# else:# lv = midlength = lv - i + 1val[i] += lengtharr[lv+2] += 1# for j in range(i,lv+1):# ans *= pow(A[j], length,MOD)# ans %= MOD# length -= 1for i in range(N+1):arr[i+1] += arr[i]n = 0cur = 0# print(val[:10])# print(arr[:10])for i in range(N):cur += val[i]cur -= n;cur += arr[i]# print(cur)ans *= pow(A[i], cur, MOD)ans %= MODn += 1print(ans)