题目描述
给定 n 个整数 a1,a2,⋅⋅⋅,an,求它们两两相乘再相加的和,即
S=a1⋅a2+a1⋅a3+⋅⋅⋅+a1⋅an+a2⋅a3+⋅⋅⋅+an−2⋅an−1+an−2⋅an+an−1⋅an
样例
4
1 3 6 9
算法1
(前缀和) $O(n^2)$
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+5;
long long q[N],p[N],o[N];
int main()
{
int m,n;
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&q[i]);
for(int i=1;i<=n;i++)
{
o[i]=o[i-1]+q[i-1];//对于前几项,列出,找出差别,然后再找相同的部分,列出公式;
p[i]=p[i-1]+o[i]*q[i];//类似求子矩阵,画图然后很清晰推出求和公式;
}
cout<<p[n];
return 0;
}