题目描述

给定 $n$ 个整数 $a _ 1, a _ 2, \ldots, a _ n$，求它们两两相乘再相加的和，即

$S = a _ 1 \cdot a _ 2 + a _ 1 \cdot a _ 3 + \ldots + a _ 1 \cdot a _ n + a _ 2 \cdot a _ 3 + \ldots + a _ {n − 2} \cdot a _ {n − 1} + a _ {n − 2} \cdot a _ n + a _ {n − 1} \cdot a _ n$

输入格式

输入的第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a _ 1, a _ 2, \ldots, a _ n$。

输出格式

输出一个整数 $S$，表示所求的和。

请使用合适的数据类型进行运算。

数据范围

对于 $30 \%$ 的数据，$1 \le n \le 1000$，$1 \le a _ i \le 100$。
对于所有评测用例，$1 \le n \le 2 \times 10 ^ 5$，$1 \le a _ i \le 1000$。

输入样例：

4
1 3 6 9

输出样例：

117

解题思路

我们对这个式子进行一个恒等变形：

$$ \begin {split} S & = a _ 1 a _ 2 + a _ 1 a _ 3 + \ldots + a _ 1 a _ n + a _ 2 a _ 3 + \ldots + a _ 2 a _ n + \ldots + a _ {n - 1} a _ n \\\ & = {a _ 1 a _ 2 + a _ 1 a _ 3 + \ldots + a _ 1 a _ n + a _ 2 a _ 1 + a _ 2 a _ 3 + \ldots + a _ 2 a _ n + \ldots + a _ n a _ 1 + a _ n a _ 2 + \ldots + a _ n a _ {n - 1} \over 2} \\\ & = {a _ 1 (a _ 2 + a _ 3 + \ldots + a _ n) + a _ 2 (a _ 1 + a _ 3 + \ldots + a _ n) + … + a _ n (a _ 1 + a _ 2 + \ldots a _ {n - 1}) \over 2} \\\ & = {a _ 1 (sum - a _ 1) + a _ 2 (sum - a _ 2) + \ldots + a _ n (sum - a _ n) \over 2} (sum = \sum _ {i = 1} ^ n a _ i) \\\ & = {\sum _ {i = 1} ^ n a _ i (sum - a _ i) \over 2} \end {split} $$

这样我们预处理 $sum$，就可以在 $\Theta (n)$ 时间内求得这个式子的值了。

还有，本题要记得开 long long （不开 long long 见祖宗）。

AC Code

#include <iostream>
#define N 200005
using namespace std;

int n, a[N];
long long sum, ans;

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i], sum += a[i]; // 输入每个数，预处理总和
    }
    for (int i = 1; i <= n; i ++)
    {
        ans += a[i] * (sum - a[i]); // 将答案累计上 a[i] * (sum - a[i])
    }
    cout << ans / 2; // 最后答案要除以 2
    return 0;
}

感谢观看！

上一篇

下一篇

$$\href {/blog/content/29204/} {\color {fuchsia} {【寒假每日一题】题解}}$$