【数学】求和

题目

4644. 求和 - AcWing题库

---

给定 $n$ 个整数 $a_1, a_2,· · ·, a_n$ ，求它们两两相乘再相加的和，即

$S = a_1 · a_2 + a_1 · a_3 + · · · + a_1 · a_n + a_2 · a_3 + · · · + a_{n−2} · a_{n−1} + a_{n−2} · a_n + a_{n−1} · a_n$

输入格式

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

第二行包含 $n$ 个整数 $a_1, a_2, · · ·, a_n$ 。

输出格式

输出一个整数 $S$ ，表示所求的和。

请使用合适的数据类型进行运算。

数据范围

对于 $30\%$ 的数据， $1 ≤ n ≤ 1000$ ， $1 ≤ a_i ≤ 100$ 。
对于所有评测用例， $1 ≤ n ≤ 200000$ ， $1 ≤ a_i ≤ 1000$ 。

输入样例：

4
1 3 6 9

输出样例：

117

解题

方法一：数学

思路

$$a_1 \times a_2 + a_1 \times a_3 + \dots + a_1 \times a_{n-1} + a_1 \times a_n + \\ \kern{44pt} a_2 \times a_3 + \dots + a_2 \times a_{n-1} + a_2 \times a_n + \\ \kern{92pt} a_{n-2} \times a_{n-1} + a_{n-1} \times a_n + \\ \kern{147.5pt} a_{n-1} \times a_n \\ \kern{190pt} = \\ \kern{76pt} a_1(a_2 + a_3 + ... + a_{n-1} + a_n) + \\ \kern{97pt} a_2(a_3 + ... + a_{n-1} + a_n) + \\ \kern{125pt} a_{n-2}(a_{n-1} + a_n) + \\ \kern{141pt} a_{n-1} \cdot a_n \\$$

$$a_1 \times a_2 + a_1 \times a_3 + \dots + a_1 \times a_{n-1} + a_1 \times a_n = \frac{\sum_{i=1}^{n}(a_i \times (\sum_{j=1}^{n}a_j - a_i))}{2}$$

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n];
        long sum = 0;
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            int x = (int) in.nval;
            a[i] = x;
            sum += x;
        }
        long ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += a[i] * (sum -= a[i]);
        }
        System.out.println(ans);
    }
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n];
        long sum = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            int x = (int) in.nval;
            ans += sum * x;
            sum += x;
        }
        System.out.println(ans);
    }
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[] a = new int[n];
        long sum = 0, squSum = 0;
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            int x = (int) in.nval;
            squSum += x * x;
            sum += x;
        }
        System.out.println((sum * sum - squSum) / 2);
    }
}