题目描述
给定 n 个整数 a1,a2,⋅⋅⋅,an,求它们两两相乘再相加的和,即
S=a1⋅a2+a1⋅a3+⋅⋅⋅+a1⋅an+a2⋅a3+⋅⋅⋅+an−2⋅an−1+an−2⋅an+an−1⋅an
输入格式
输入的第一行包含一个整数 n。
第二行包含 n 个整数 a1,a2,⋅⋅⋅,an。
输出格式
输出一个整数 S,表示所求的和。
请使用合适的数据类型进行运算。
数据范围
对于 30% 的数据,1≤n≤1000,1≤ai≤100。
对于所有评测用例,1≤n≤200000,1≤ai≤1000。
算法1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
ll n; cin >> n;
ll sum = 0, a[n], ans = 0
for(int i=0; i<n; i++) {
cin >> a[i], sum += a[i];
}
for(int i=0; i<n; i++) {
ans += a[i] * (sum - a[i]);
}
cout << ans / 2 << endl;
return 0;
}
----------
对于题中算式,我们反过来计算,重新组合计算顺序,会发现相当于每一个数乘上其前面的前缀和
### 算法2
include[HTML_REMOVED]
using namespace std;
using ll =long long;
ll sum,ans;
int arr[200010];
int main(){
int n;cin>>n;
for(int i=0;i<n;i++){
int x;
cin>>x;
ans+=sum*x;
sum+=x;
}
cout<<ans<<endl;
}
```