ABC 401-500/ABC405C - Sum of Product - 競技プログラミング用 知識集積所

---

問題

ABC405C

必要知識

B以下レベルの内容は省略

• 累積和

考え方

愚直に計算すると、nが3*10^5の場合、ほぼ4.5*10^10パターンの総和を計算することになり圧倒的に間に合わない。
そこで、手計算で式をこのように変形する。

(A1*A2 + A1*A3 + A1*A4 + …… + A1*An) + (A2*A3 + A2*A4 + …… + A2*An) + …… + (A(n-1)*An)
= (A1*A2) + (A1*A3 + A2*A3) + (A1*A4 + A2*A4 + A3*A4) + …… + (A1*An + A2*An + …… + A(n-1)*An)
= (A1)*A2 + (A1+A2)*A3 + (A1+A2+A3)*A4 + …… + (A1+A2+……+A(n-1))*An

すると、括弧内がただの累積和になっている。

したがって、O(n)で累積和のvector（未作成）を作成し、それを参照しながら総和を計算すればO(n)で計算が完了する。

解答例

解答例

注意点

long long型を用いること。

nが最大で、各aも最大だと、累積和の最後の方がint型から溢れる。
累積和をlong long型で作ること。
partial_sum関数を用いる場合は、a自体をlong long型にする必要がある。

別解

異なる計算方法を利用する。

「異なる2つの積、全パターンの合計」は、「(合計の2乗-2乗の合計)/2」で求められる。
その方がコードも簡単。
合計の2乗が最大で9*10^18になり超ギリギリだがlong long型から溢れない。
解答例