Acwing-4644. 求和

暴力解法，TLE了hh~

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 200010;

int n;
int a[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
    
    int sum = 0;
    for (int i = 0; i < n; ++ i)
        for (int j = i + 1; j < n; ++ j)
            sum += a[i] * a[j];
    
    printf("%d", sum);
    
    return 0;
}

应用前缀和的思想，让a[i]乘以它前面的所有数即可，即

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

int n;

int main()
{
    scanf("%d", &n);
    
    LL res = 0, s = 0;
    while (n --)
    {
        int x;
        scanf("%d", &x);
        res += x * s;
        s += x;
    }
    
    printf("%lld", res);
    return 0;
}

观察题目中的公式，我们发现该式可扩充为(a1 + a2 + a3 + ... + an) ^ 2 这种完全平方的形式，然后减去扩充的那部分即为题中所求公式的值

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

int n;

int main()
{
    scanf("%d", &n);
    
    LL s1 = 0, s2 = 0;
    while (n --)
    {
        int x;
        scanf("%d", &x);
        
        s1 += x;
        s2 += x * x;
    }
    
    printf("%lld", (s1 * s1 - s2) / 2);
    return 0;
}