AtCoder Beginner Contest 177 C問題「Sum of product of pairs」解説(Python3,C++,Java)

注意)解答例はPython3のみ出来ております。C++,Javaの方は「全ての提出」からコードを見て実装することをおすすめします。

皆さんこんにちは(コンテスト後の方はこんばんは！)Ruteです！

AtCoder Beginner Contest 177 C問題の解説をこれから始めます！
A問題,C問題の解説は以下のリンクより見ることが出来ますのでご確認下さい！！

各問題の解説

A問題	B問題	C問題
準備中	準備中	この記事です

問題概要

$N$個の整数$A_1,...A_N$で構成された数列が与えられる。
$1 \leq i < j \leq N$を満たす全ての組$(i,j)$についての$A_i×A_j$の和を$mod(10^9+7)$で求めよ。

問題URL :https://atcoder.jp/contests/abc177/tasks/abc177_c

制約

・$2 \leq N \leq 2×10^5$
・$0 \leq A_i \leq 10^9$
・入力は全て整数

解説

$A_1,...A_N$のうち、$(i,j)$の組は$(N-1)+(N-2)+....1$組あり、$\frac{N(N-1)}{2}$組あることが分かります。これらを$1$個ずつ考え計算していくと$O(N^2)$の計算量が必要になります。
一般的に、コンピューターで1秒間に処理できる計算回数はおよそ$10^8$回(1億回)なので制約上、この計算量では実行時間制限を超過してしまいます。

ここで、問題を別の視点で考えてみましょう。

入力例1・出力例1では、答えは$11$ですが、

答えについて、

\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j

になることが分かっています。

そこで、まずは $\sum_{j = i+1}^{N} A_j$について求めることを考えます。

ここで用いるテクニックは 累積和と呼ばれるものです。

累積和とは、あらかじめ初項からある項までの和を求め、それについての数列を作るというものです。

累積和で作成する数列の例としては、
数列$B$ : ($B_1,B_2, ... B_N$)が与えられた時、
$[0 , \sum_{i = 1}^{1} B_i , \sum_{i = 1}^{2} B_i , ... \sum_{i = 1}^{N} B_i ]$
というものがあります。

詳しくは、けんちょんさんの累積和の記事をご覧下さい。

今回、考える累積和としては、長さ$N-1$の数列
$[\sum_{j = 2}^{N} A_j , \sum_{j = 3}^{N} A_j , ... \sum_{j = N}^{N} A_j]$
です。
これは、数列Aの総和から$A_{j-1}$を引き続けて、その都度数列に値を挿入し続ければ作成することが出来ます。

これで、$\sum_{j = i+1}^{N} A_j$ の数列が出来ました。この数列を$C$とおくことにします。

次に、

\sum_{i = 1}^{N-1} \sum_{j = i+1}^{N} A_i A_j

を求めるために、各$i(1 \leq i \leq N-1)$について$A_i × C_i$を計算します。
その値を、求める答えの値に加算していきます。

最後に、答えの値を$(10^9+7)$で割ったあまりを出力すれば良いです。

ここで、Pythonの場合は多倍長整数に対応しているのでその都度答えを$(10^9+7)$で割らなくても良いですが、C++やJavaの場合は、計算の途中で64bit整数型の範囲よりも答えが大きくなる可能性があります。(longやlong long intなど)(いわゆるオーバーフローと呼ばれるものです)

なぜなら、 $2^{63}-1 \simeq 9.22×10^{18}$となりますが、$A_i$の制約より、$10^{18}$を$10$回以上足すケースがあることも考えられるからです。

結局、求める値は足したあとその都度$10^9+7$で割った余りにし続けても最終的には同じになるので、$10^9+7$で割った余りにし続ければオーバーフローを気にしなくてもよくなります。

計算量は累積和の処理で$O(N)$, 各$i(1 \leq i \leq N-1)$について$A_i × C_i$を計算するときに$O(1)$かかるので、$O(N)$となります。

以下、Pyhton3,C++,Javaでの解答例を示します.
(8/30 11:29時点　Python3の解答例のみ示しています。C++,Javaは準備ができ次第作成しますので、更新をお待ち頂きたいと思います)

Python3での解答例

ABC177C.py

N = int(input()) #入力する整数
A = list(map(int,input().split())) #入力する数列A
SUMA = sum(A) #数列の和
MOD = 10**9 + 7 # mod
C = [0] * (N-1) #累積和数列
for i in range(N-1): #\sum_{j = i+1}^{N}を求めて数列に代入する
  SUMA -= A[i]
  C[i] = SUMA
ans = 0 #求める答え
for i in range(N-1):
  ans += A[i]*C[i]
  ans %= MOD #その都度modで割った余りにする
print(ans) #答えを出力する

#計算量はO(N)です。

C++での解答例

準備中です

Javaでの解答例

準備中です