题解：AT_abc405_c [ABC405C] Sum of Product

· · 题解

公式

计算 \displaystyle \sum_{1\leq i<j\leq N} A_iA_j 的公式为：

\sum_{1 \leq i < j \leq N} A_i A_j = \frac{1}{2} \left( \left( \sum_{i=1}^N A_i \right)^2 - \sum_{i=1}^N A_i^2 \right)

推导

先将所有元素和的平方分解一下：

\left( \sum_{i=1}^N A_i \right)^{2} = \sum_{i=1}^N A_i^2 + 2 \sum_{1 \leq i < j \leq N} A_i A_j

然后，我们发现后面那一项包含了题目的求式，所以把它提出来：

2 \sum_{1 \leq i < j \leq N} A_i A_j = \left( \sum_{i=1}^N A_i \right)^2 - \sum_{i=1}^N A_i^2

接着再化简：

\sum_{1 \leq i < j \leq N} A_i A_j = \frac{1}{2} \left( \left( \sum_{i=1}^N A_i \right)^2 - \sum_{i=1}^N A_i^2 \right)

就得到公式了。

// code
#include<bits/stdc++.h>
using namespace std;

const int N = 3e5 + 10;
int a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int sum = 0, s = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        s += a[i] * a[i];
    }
    cout << (sum * sum - s) / 2 << endl;
    return 0;
}