No.1084 積の積
タグ : / 解いたユーザー数 181
作問者 :
tyawanmusi
/ テスター :
kichi2004_
問題文
要素数 $N$ の非負整数列 $A$ があります。 $A$ の $i(1 \le i \le N)$ 番目の要素は $A_i$ です。
関数 $f(l,r)(1 \le l \le r \le N)$ を次のように定義します。
- $f(l,r)=A_l \times A_{l+1} \times \dots \times A_r$
茶碗蒸しくんは、答えが $10^9$ 以上になると必ず計算ミスをしてしまいます。
茶碗蒸しANOTHERくんは一切計算ミスをしません。
茶碗蒸しくんは $N(N+1)/2$ 通りある $(l,r)(1 \le l \le r \le N)$ すべてについて $f(l,r)$ を計算し、メモ帳に書き残しました。
茶碗蒸しANOTHERくんは、茶碗蒸しくんが求めた $N(N+1)/2$ 個の数から計算結果が間違っている数を消しました。
そして、茶碗蒸しANOTHERくんは残った数を全て掛け合わせ、その答えを茶碗蒸し神に奉納しました。
茶碗蒸しANOTHERくんが奉納した数を求めてください。
ただし、答えはとても大きな数になることがあるので、答えを $10^9+7$ で割ったあまりを出力してください。
21:48編集：問題文中の「数字」→「数」に統一
制約
- $N,A_i$は整数
- $1 \le N \le 10^5$
- $0 \le A_i < 10^9$
入力
$N$
$A_1\ A_2\ \dots\ A_n$
$1$ 行目には $N$ が入力されます。
$2$ 行目には $A$ が空白区切りで入力されます。
出力
答えを整数で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3
2 3 5
出力
81000
茶碗蒸しくんは、 $(2,3,5,6,15,30)$ をメモ帳に書きました。 茶碗蒸しANOTHERくんは、これらの総乗である $81000$ を求めました。
サンプル2
入力
3
100000 100000 100000
出力
993000007
茶碗蒸しくんは $(10^5,10^5,10^5,10^{10},10^{10},10^{15})$ をメモ帳に書きたかったですが、 $(10^{10},10^{10},10^{15})$ の部分で計算ミスをしてしまいました。
茶碗蒸しANOTHERくんはその部分を消すので、 $10^5 \times 10^5 \times 10^5$ を計算しました。
答えを $10^9+7$ で割ったあまりを出力してください。
サンプル3
入力
10
1 2 3 4 5 6 7 8 9 10
出力
29831907
答えを $10^9+7$ で割ったあまりを出力してください。
サンプル4
入力
5
31415 92653 1333 58979 32384
出力
282377886
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。