【ABC177 C】「Sum of product of pairs」を解く【Python3】

「AtCoder」解説一覧へ

N個の整数 A1,…,ANについて、1≦i<j≦N を満たす全ての組(i, j)についての「Ai×Aj」の和を mod(109+7)で求める問題です。

提出
n = int(input())
a = list(map(int, input().split()))
su = sum(a)
ans = 0

for i in range(n-1):
    su -= a[i]
    ans += (a[i]*su)

print(ans%(10**9+7))

jはiより大きいことに注目します。

すると、Aiとの組み合わせの和は、

Ai×(Ai+1+Ai+2+Ai+3+…)

となるので、すべてのiに対してこの計算を行い、足していきます。

最初に数列aの合計値を出しておき、毎回a[i]を引いておくことで、「i<j」を実現できます。

答えに、mod(109+7)の処理をしたものを出力します。

【ABC177】解説記事リスト

「AtCoder」解説一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です