自动搬运

查看原文

来自洛谷，原作者为

	NightFire666 人生如此复杂，机会多得像稠密图，我们没理由认输。尽管我们走不了最短路，但图仍是连通图。TLE之前，没有一个节点叫失败。 ʕ̯•͡˔•̯᷅ʔ

搬运于2025-08-24 22:42:19，当前版本为作者最后更新于2023-07-22 22:08:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到大佬们的前缀和代码，本蒟蒻自愧不如 qwq。

本题也可以用 完全平方公式！！！

推荐使用 博客 食用！

咳咳，先从一个简单的例子入手：

在 $1$，$2$，$3$，$4$，$5$，$6$，$7$，$8$，$9$，$10$ 这些正整数中每两个数相乘的乘积之和是多少？

我们都知道这十个数两两相乘的乘积有 $C_{10}^2=45$ 个，有多项式：

$$\frac{(1+2+3+ \cdots +9+10)^2-(1^2+2^2+3^2+ \cdots +9^2+10^2)}{2} $$

为这十个数两两相乘的乘积之和。

• 为什么？

先看一下下面的算式：

$$(1+2+3+ \cdots +9+10)^2$$

由完全平方公式展开后为：

$$(1^2+2^2+3^2+ \cdots +9^2+10^2)+2 \times (1 \times 2+1 \times 3+ \cdots 9 \times 10) $$

不难发现多项式 $(1 \times 2+1 \times 3+ \cdots 9 \times 10)$ 正是要求的答案！

易得：

$$(1 \times 2+1 \times 3+ \cdots 9 \times 10)=\frac{(1+2+3+ \cdots +9+10)^2-(1^2+2^2+3^2+ \cdots +9^2+10^2)}{2} $$

那么本题的公式就是：

$$\frac{(a_1+a_2+a_3+ \cdots +a_{n-1}+a_n)^2-({a_1}^2+{a_2}^2+{a_3}^2+ \cdots +{a_n}^2)}{2} $$

最后送上代码！

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,mul=0,sum=0;
//mul:和的平方
//sum:平方的和
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        sum+=(x*x);
        mul+=x;
    }
    cout<<(mul*mul-sum)/2;
    return 0;
}