結果
問題 |
No.1084 積の積
|
ユーザー |
|
提出日時 | 2021-03-17 22:44:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 1,052 bytes |
コンパイル時間 | 771 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 88,832 KB |
最終ジャッジ日時 | 2024-11-15 17:26:43 |
合計ジャッジ時間 | 5,752 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 27 |
ソースコード
def syakutori(A): total=1 def merge(total,Ai): total*=Ai return total def inv_merge(total,Ai): total//=Ai return total def is_possible_merge(total,Ai): return total*Ai<10**9 N=len(A) left, right, right_max=0,0,N res=1 T=1 S=1 for left in range(right_max): while right<right_max and is_possible_merge(total,A[right]): total = merge(total,A[right]) S*=A[right] S%=MOD T*=S T%=MOD right+=1 res*=T res%=MOD if right==left: right+=1 else: total = inv_merge(total,A[left]) S*=pow(A[left],MOD-2,MOD) S%=MOD T*=pow(A[left],MOD-1-(right-left),MOD) T%=MOD return res ######################################### import sys input = sys.stdin.readline K=10**9 MOD=10**9+7 N=int(input()) A=list(map(int, input().split())) if 0 in A: print(0) else: res=syakutori(A) print(res)