P8772 [蓝桥杯 2022 省 A] 求和

题目描述

给定 n 个整数 1,2,⋯ ,a1,a2,⋯,an, 求它们两两相乘再相加的和，即

S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅an

输入格式

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

第二行包含 n 个整数 1,2,⋯a1,a2,⋯an 。

输出格式

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

输入输出样例

输入

4
1 3 6 9

输出 #1复制

说明/提示

对于 30%30% 的数据, 1≤n≤1000,1≤ai≤100 。

对于所有评测用例,1≤n≤2×105,1≤ai≤1000 。

蓝桥杯 2022 省赛 A 组 C 题。

思路

利用前缀和的知识，用sum维护一个前缀和数组

S=a1⋅a2+a1⋅a3+⋯+a1⋅an+a2⋅a3+⋯+an−2⋅an−1+an−2⋅an+an−1⋅an=(a2+a3+⋯+an)⋅a1+(a3+a4+⋯+an)⋅a2+⋯+an⋅an−1

由公式推导，最终只需要从1到n-1遍历一次a数组，将a[i] * (sum[n] - sum[i])的值累加到ans中即可

#define _for(i,a,b) for(int i=a;i<b;i++)
#define ll long long
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
ll s;
ll n;
ll a[N];
ll sum[N];
int main()
{
	cin >> n;
	_for(i, 1, n + 1) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	_for(i, 1, n) {
		s += a[i] * (sum[n] - sum[i]);
	}
	cout << s << endl;
	return 0;
}