1. 2023: [蓝桥杯2022初赛] 求和

传送门：http://oj.ecustacm.cn/problem.php?id=2023

1.1. 题意

给定数组$a$，求$\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j$。

1.2. Tag

前缀和

1.3. 难度

☆☆

1.4. 思路

可以进行如下转换：

$\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j =\sum_{i=1}^n\left[a_i\sum_{j=i+1}^na_j\right]$

对于里面的求和，直接用前缀和优化：

$\sum_{i=1}^n\sum_{j=i+1}^n a_ia_j =\sum_{i=1}^n\left[a_i\sum_{j=i+1}^na_j\right] =\sum_{i=1}^n a_i(sum[n]-sum[i])$

预处理前缀和即可，时间复杂度$O(n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
ll a[maxn], sum[maxn];
int main(){
    int n;
    ll ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++) ///预处理前缀和
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    for(int i = 1; i <= n; i++) ///求和即可
        ans += a[i] * (sum[n] - sum[i]);
    cout<<ans<<endl;
    return 0;
}