题解

绝对值在平方后不会影响结果，因此每对音叉产生的差异能量可以直接写成 $(a_i-a_j)^2$．

算法 0：枚举数对

枚举所有 $i<j$，把 $(a_i-a_j)^2$ 加入答案并及时取模．时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$．

预期通过 subtask 1、2，预期得分为 $30$ 分．

算法 1：按照数值统计

当 $a_i\in\{0,1\}$ 时，只有数值不同的数对产生贡献，答案等于零的数量乘以一的数量，再对 $10^9+7$ 取模．预期通过 subtask 3，预期得分为 $15$ 分．

当 $0\le a_i\le1000$ 时，可以统计每个值的出现次数 $c_x$，再枚举两个不同的值：

$$\sum_{0\le x<y\le1000}c_xc_y(x-y)^2.$$

时间复杂度为 $O(n+V^2)$，其中 $V=1001$，空间复杂度为 $O(V)$．这也包含二值序列的情况．

预期通过 subtask 3、4，预期得分为 $30$ 分．

算法 2：展开平方

先展开每个数对的贡献：

$$(a_i-a_j)^2=a_i^2+a_j^2-2a_ia_j.$$

在所有无序数对中，每个 $a_i^2$ 恰好出现 $n-1$ 次，因此

$$\sum_{i<j}(a_i^2+a_j^2)=(n-1)\sum_{i=1}^{n}a_i^2.$$

另一方面，平方和满足

$$\left(\sum_{i=1}^{n}a_i\right)^2 =\sum_{i=1}^{n}a_i^2+2\sum_{i<j}a_ia_j.$$

将两式合并，可以得到

$$\sum_{i<j}(a_i-a_j)^2 =n\sum_{i=1}^{n}a_i^2-\left(\sum_{i=1}^{n}a_i\right)^2.$$

扫描序列时维护 $S=\sum a_i$ 和 $Q=\sum a_i^2$，最终计算 $nQ-S^2$ 并将负余数调整到 $[0,10^9+7)$ 即可．

不能先用整数保存未经取模的 $S$ 和 $Q$：完整数据中 $S$ 可以达到 $10^{15}$，$S^2$ 已经远超 64 位整数范围．实现时应让每个读入值先对模数取模，并在每次加法后维护 $S,Q$ 的余数．此时单次乘法的两个因子都小于 $10^9+7$，使用 64 位有符号整数即可安全完成乘法．另外，C++ 中负数取模仍可能为负，因此最终答案小于 $0$ 时要加一次模数．大量重复值不需要特殊处理，相等数对的贡献会在公式中自然抵消．

正确性证明

平方展开对每个数对都成立；汇总后，每个平方项和每个乘积项出现的次数均由上面两条等式精确统计．因此最终公式与题目要求的所有数对贡献之和完全相等，取模不会改变同余结果，算法正确．

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$．

预期通过所有 subtask，预期得分为 $100$ 分．

参考代码

#include <cstdint>
#include <iostream>

constexpr std::int64_t MOD = 1000000007LL;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::int64_t n;
    std::cin >> n;
    std::int64_t sum = 0;
    std::int64_t square_sum = 0;
    for (std::int64_t i = 0; i < n; ++i) {
        std::int64_t x;
        std::cin >> x;
        x %= MOD;
        sum += x;
        if (sum >= MOD) sum -= MOD;
        square_sum = (square_sum + x * x) % MOD;
    }
    std::int64_t answer = ((n % MOD) * square_sum - sum * sum) % MOD;
    if (answer < 0) answer += MOD;
    std::cout << answer << '\n';
    return 0;
}