Sum of product of pairs
/icons/hr.icon
問題
/icons/hr.icon
出典
ABC177 - C 386 diff
/icons/hr.icon
問題文
$ N 個の整数 $ A_1, ... , A_Nが与えられます。
$ 1 \leq i < j \leq N を満たす全ての組 $ (i, j) についての $ A_i \times A_j の和を mod($ 10^9 + 7) で求めてください。
/icons/hr.icon
制約
$ 2 \leq N \leq 2 \times 10^5
$ 0 \leq A_i \times 10^9
/icons/hr.icon
出力
$ \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} A_i A_j を $ mod (10^9 + 7) で出力せよ。
/icons/hr.icon
解法
方針：与えられた式を変形してみる
$ \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} A_i A_j
$ = \{ A_1 \times (A_2 + A_3 + ... + A_N) \} + \{ A_2 \times (A_3 + A_4 + ... + A_N) \} + ... + \{ A_{N - 2} \times (A_{N - 1} + A_N)\} + \{ A_{N - 1} \times (A_N) \}
この式を見てみると、$ ( \quad ) で囲まれた中身は $ A_2 を始めとして、前から順に $ 1 つずつ消えていっていることがわかる。
したがって、あらかじめ、$ sum\_ := A_1 + A_2 + A_3 + ... + A_N と定義しておき、 $ forループで毎回 $ A_i \quad ( 1 \leq i \leq N - 1) を $ sum\_ から削除していけばこの問題は解くことができました。
/icons/hr.icon
コード
code:python
N = int(input())
A = list(map(int, input().split()))
sum_ = sum(A)
ans = 0
mod = 10 ** 9 + 7
for i in range(N - 1):
ans %= mod
print(ans)