题目描述
给定 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。
样例
输入样例:
4
1 3 6 9
输出样例:
117
算法1
(前缀和) O(n)
利用前缀和数组对乘法过程简化,因为每个数要互相乘以下,则每一个数一个数乘以后面数之和
时间复杂度
O(n)
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL a[N];
int b[N];
int main()
{
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++){
cin >> b[i];
a[i] = a[i - 1] + b[i];
}
LL ans = 0;
for(int i = 1 ; i <= n ; i ++){
ans += (a[n] - a[i]) * b[i];
}
cout << ans;
}