专栏文章

题解：AT_abc405_c [ABC405C] Sum of Product

llinjinkun
AT_abc405_c题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mipb57j9
此快照首次捕获于
2025/12/03 09:07
3 个月前
此快照最后确认于
2025/12/03 09:07
3 个月前
查看原文
题目是要求 ∑i=1n∑j=i+1naiaj\sum_{i = 1}^n\sum_{j = i+1}^na_ia_j，实际上就是 ∑i=1nai(∑j=i+1naj)\sum_{i = 1}^na_i(\sum_{j = i+1}^na_j)，然后发现 ∑j=i+1naj\sum_{j = i+1}^na_j 可以用前缀和维护，于是就没了。 代码：
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...