题解：AT_abc405_c [ABC405C] Sum of Product

linjinkun · 2025-05-13 21:27:52 · 题解

题目是要求 \sum_{i = 1}^n\sum_{j = i+1}^na_ia_j，实际上就是 \sum_{i = 1}^na_i(\sum_{j = i+1}^na_j)，然后发现 \sum_{j = i+1}^na_j 可以用前缀和维护，于是就没了。 代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int a[N];
long long sum[N];
signed main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i = n;i;i--)
    {
        sum[i] = sum[i+1]+a[i];
    }
    long long num = 0;
    for(int i = 1;i<n;i++)
    {
        num+=(long long)a[i]*sum[i+1];
    }
    printf("%lld",num);
    return 0;
}