結果
問題 |
No.1084 積の積
|
ユーザー |
|
提出日時 | 2020-06-20 18:34:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 409 ms / 2,000 ms |
コード長 | 604 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,032 KB |
実行使用メモリ | 102,388 KB |
最終ジャッジ日時 | 2024-07-03 17:31:18 |
合計ジャッジ時間 | 8,299 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) MOD = 10**9+7 if 0 in A: print(0) exit() acc1 = [1] acc2 = [1] for i in range(N): acc1.append(acc1[-1]*pow(A[i], N-i, MOD)%MOD) acc2.append(acc2[-1]*A[i]%MOD) now = 1 r = 0 ans = 1 for l in range(N): while r<N and now*A[r]<10**9: now *= A[r] r += 1 t = acc2[r]*pow(acc2[l], MOD-2, MOD)%MOD ans *= acc1[r]*pow(acc1[l], MOD-2, MOD)*pow(pow(t, N-r, MOD), MOD-2, MOD) ans %= MOD if l==r: r += 1 else: now //= A[l] print(ans)