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

「AtCoder」解説一覧へ

N個の整数 A₁,…,A_Nについて、1≦i<j≦N を満たす全ての組(i, j)についての「A_i×A_j」の和を mod(10⁹+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より大きいことに注目します。

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

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

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

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

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

【ABC177】解説記事リスト

【ABC177 A】「Don’t be late」を解く【Python3】

【ABC177 B】「Substring」を解く【Python3】

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

【ABC177 D】「Friends」を解く【Python3】

「AtCoder」解説一覧に戻る