[AtCoder] ABC 177 C – Sum of product of pairs

問題

方針

与えられた式は、

\[
\sum_{i = 1}^{n – 1} \sum_{j = i + 1}^{n} A_iA_j= \sum_{i = 1}^{n – 1}A_i \sum_{j = i + 1}^{n} A_j\\
\]

となるので、\( B_i = A_1 + A_2 + \cdots + A_i \) とすると、

\[
\sum_{i = 1}^{n – 1} \sum_{j = i + 1}^{n} A_iA_j= \sum_{i = 1}^{n – 1}A_i(B_n – B_{i})\\
\]

となります。よって、あらかじめ累積和を計算してから求めます。注意として、\( B_n – B_{i} \) が計算仕方によってマイナスとなる可能性があるので、

\[(B_n – B_i + 10^9 + 7 \bmod (10^9+7))\]

とします。

コード