一、题目
1、原题链接
4644. 求和 - AcWing题库
2、题目描述
给定 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。
输入样例：
4
1 3 6 9
输出样例：
117
二、解题报告
1、思路分析
1）直接枚举，暴力求解时间复杂度为O(n^2)，最坏情况要循环10^10左右，所以必定超时，无法暴力。
2）通过对式子简单分析可知，总和为第i项（i=1,2,3，....,n-1）乘（前n项前缀和-前i项前缀和），然后再求和，就可得到总和。
3）优化后的算法的时间复杂度为O(n)。
4）利用上述推导直接模拟即可。
其他思路：
思路来源：y总，今年有瓜分1万AC币的活动吗？每日一题_哔哩哔哩_bilibili
y总yyds
利用公式 ((a1+a2+...+an)^2-(a1^2+a2^2+...+an^2))/2 直接求解
2、时间复杂度
时间复杂度O(n)
3、代码详解
#include <iostream>
using namespace std;
long long a[200010];
long long s[200010];
int main()
{ long long n;
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
long long sum=0;
s[0]=a[0];
for(int i=1;i<n;i++){
s[i]=s[i-1]+a[i];
}
for(int i=0;i<n;i++){
sum+=a[i]*(s[n-1]-s[i]);
}
cout<<sum;
return 0;
}
