ほぼ日刊競プロ ABC177 C - Sum of product of pairs

C - Sum of product of pairs

問題文
N 個の整数 A
1,…,ANが与えられます。
1≤i<j≤N を満たす全ての組 (i,j) についての Ai​×Aj​の和を mod(10^9+7) で求めてください。

考えたこと

普通に２重for文ではタイムオーバーしてしまうため，効率よく計算する方法を考える．

sum = A1*A2+A1*A3+A1*A4+A2*A3+A3*A4〜
という感じなので（）がつけられるところを探す．
sum = A1(A2+A3+A4)＋A2(A3+A4)+A3*A4
A2＋A3+A4〜Anの合計は(A1+A2＋A3+A4〜An)-A1となる．
A3+A4〜Anの合計は(A2＋A3+A4〜An)-A2となる．
つまり一個前の計算が次の計算にそのまま使うことができる．

一旦sumを計算した後にA1を引いて括弧の外側のA1を掛けて，足していく．
これならばn回の思考で終わるため間に合う．

N = int(input())
Alist = list(map(int,input().split()))
temp = 10**9+7
ans = 0
sumans = sum(Alist)
for i in range(N):
   sumans-=Alist[i]
   ans+=sumans*Alist[i]
print (ans%temp)