C++
$\color{gold}{— > 蓝桥杯辅导课题解}$
算法1:
思路:
前缀和
题中公式:
s = $a_1$ * $a_2$ + $a_1$ * $a_3$ + ··· + $a_1$ * $a_n$ + $a_2$ * $a_3$ + ··· + $a_2$ * $a_n$ + ··· $a_{n-1}$ * $a_n$
$\hspace{1.5em}a_1$ * ($a_2$ + $a_3$ + ··· + $a_n$) + $a_2$ * ($a_3$ + ··· + $a_n$) + ··· $a_{n-1}$ * $a_n$
$\large\color{red}{前缀和:}$ $\hspace{3em}s_n$ - $s_1$ $\hspace{4em}s_n$ - $s_2$ ···
由此,得出公式:
s = $a_1$ * ($s_n$ - $s_1$) + $a_2$ * ($s_n$ - $s_2$) + ··· $a_{n-1}$ * ($s_n$ - $s_{n-1}$)
$code:$
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
typedef long long ll;
int n;
ll a[N], s[N]; // s : 前缀和数组
int main() {
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> a[i], s[i] = s[i - 1] + a[i];
ll sum = 0;
for (int i = 1; i <= n; i ++)
sum += a[i] * (s[n] - s[i]);
cout << sum;
return 0;
}
算法2:
思路:
推导
$a_1$, $a_2$, $a_3$, $a_4$ 四个数则有:$a_1$ * $a_2$ + $a_1$ * $a_3$ + $a_1$ * $a_4$ + $a_2$ * $a_3$ + $a_2$ * $a_4$ + $a_3$ * $a_4$
由后向前看:
$a_4$ * ($a_1$ + $a_2$ + $a_3$)
$a_3$ * ($a_1$ + $a_2$)
$a_2$ * ($a_1$)
$a_1$ * (0)
$\color{blue}{即当前项乘上它前面所有数的和}$
$code:$
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll s, sum;
int main() {
cin >> n;
while (n --) {
int x; cin >> x;
sum += s * x;
s += x; // 前面所有数的和
}
cout << sum;
return 0;
}
Orz