ABC177 C – Sum of product of pairs

はじめに

競プロの精進のために学びがあった問題についてまとめています。 目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC177 C – Sum of product of pairsを解きました。

難易度はほぼ茶色の灰色。

考察

全探索はO(N^2)になるのでむり。

ここで、求める解は(Ai*Aj)の総和であることから、あるi=1に対して以下の式が成り立つことを確認する。

i=1のときの(AiAj)の総和 ＝ Ai (A2+A3…+AN)

上記の式がすべてのiについて当てはまることから、計算量O(N)で求めることができる

コード

N = int(input())
A = list(map(int,input().split()))

jsum = 0
for a in A:
    jsum += a

ans = 0
M = pow(10,9) + 7
for i in range(N-1):
    jsum -= A[i]
    ans += A[i] * jsum
    ans %= M

print(ans)

まとめ

気づいてしまえばEasyな問題だったものの少し時間がかかってしまった。

累積和の問題は区間和の総和で求めていくと1000回唱える。