算法1

(数学) $O(n*MaxA)$

注意到 $\mid A_i \mid \leqslant 200$。虽然 $N$ 很大，但两数之间的差值很小，所以可以先统计 $D_k$， 即 $A_i = k$ 的次数。而 $A_i$ 可能出现负数不能作为数组下标，所以需要在 $A_i$ 的基础上加上 $MaxA$。
于是原来的第二重循环就可以变成枚举所有的 $A_j([-200, 200])$，把 $(A_i - A_j)^2 * D[MaxA + A_j]$ 累加到答案中即可。

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

const int MaxA = 200;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<int> d(MaxA * 2 + 1);
    ll ans = 0;
    rep(i, n) {
//      rep(j, i) {
//          int x = a[i] - a[j];
//          ans += x * x;
//      }
        for (int aj = -MaxA; aj <= MaxA; ++aj) {
            int c = d[MaxA + aj];
            int x = a[i] - aj;
            ans += (ll)x * x * c;
        }
        d[MaxA + a[i]]++;
    }

    cout << ans << '\n';

    return 0;
}

// O(n + (MaxA)^2)
// 利用 (Ai - Aj)^2 = (Aj - Ai)^2
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

const int MaxA = 200;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<int> d(MaxA * 2 + 1);
    rep(i, n) d[MaxA + a[i]]++;
    ll ans = 0;
    for (int ai = -MaxA; ai <= MaxA; ++ai) {
        for (int aj = -MaxA; aj < ai; ++aj) {
            ll x = ai - aj;
            ans += x * x * d[MaxA + ai] * d[MaxA + aj];
        }
    }

    cout << ans << '\n';

    return 0;
}

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

const int MaxA = 200;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<int> d(MaxA * 2 + 1);
    rep(i, n) d[MaxA + a[i]]++;
    ll ans = 0;
    rep(ai, d.size()) {
        rep(aj, ai) {
            ll x = ai - aj;
            ans += x * x * d[ai] * d[aj];
        }
    }

    cout << ans << '\n';

    return 0;
}

算法2

(数学) $O(n)$

注意到，$\displaystyle \sum_{i = 2}^n\sum_{j = 1}^{i - 1} (A_i - A_j)^2 * 2 = \sum_{i = 1}^n\sum_{j = 1}^n (A_i - A_j)^2$
而
$$ \begin{aligned} \sum_{i = 1}^n\sum_{j = 1}^n (A_i - A_j)^2 &= \sum_{i = 1}^n\sum_{j = 1}^n (A_i^2 + A_j^2 - 2A_iA_j)\\\ &= \sum_{i = 1}^n\sum_{j = 1}^n A_i^2 + \sum_{i = 1}^n\sum_{j = 1}^n A_j^2 - 2\sum_{i = 1}^n\sum_{j = 1}^n A_iA_j \\\ &= 2n\sum_{i = 1}^n A_i^2 - 2\left(\sum_{i = 1}^n A_i\right)^2 \end{aligned} $$

关于 $\displaystyle \sum_{i = 1}^n\sum_{j = 1}^n A_iA_j = \left(\sum_{i = 1}^n A_i\right)^2$ 的证明如下：

不妨记 $\displaystyle S = \sum_{i = 1}^n A_i^2$，于是 $\displaystyle \sum_{i = 1}^n\sum_{j = 1}^n A_iA_j = \sum_{i = 1}^n \left(A_i \sum_{j = 1}^n A_j\right) = \sum_{i = 1}^n (A_i S) = S\sum_{i = 1}^nA_i = S^2$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::vector;
using ll = long long;

const int MaxA = 200;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    ll s = 0;
    rep(i, n) cin >> a[i], s += a[i];

    ll ans = 0;
    rep(i, n) ans += a[i] * a[i];
    ans *= n;
    ans -= s * s;

    cout << ans << '\n';

    return 0;
}