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

2020年12月14日

問題

方針

与えられた式は、

\[
\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))\]

とします。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll mod = 1000000007;
    
    ll B[N + 1]{};
    for (int i = 0; i < N; i++) {
        B[i + 1] = (B[i] + A[i]) % mod;
    }
    ll ans = 0;
    for (int i = 0; i < N - 1; i++) {
        ans += A[i] * (B[N] - B[i + 1] + mod);
        ans %= mod;
    }
    cout << ans << "\n";
    return 0;
}