侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学】求和

GabrielxD
2023-01-13 / 0 评论 / 0 点赞 / 61 阅读 / 937 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-13,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

4644. 求和 - AcWing题库


给定 nn 个整数 a1,a2,,ana_1, a_2,· · ·, a_n ,求它们两两相乘再相加的和,即

S=a1a2+a1a3++a1an+a2a3++an2an1+an2an+an1anS = 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

输入格式

输入的第一行包含一个整数 nn

第二行包含 nn 个整数 a1,a2,,ana_1, a_2, · · ·, a_n

输出格式

输出一个整数 SS ,表示所求的和。

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

数据范围

对于 30%30\% 的数据, 1n10001 ≤ n ≤ 10001ai1001 ≤ a_i ≤ 100
对于所有评测用例, 1n2000001 ≤ n ≤ 2000001ai10001 ≤ a_i ≤ 1000

输入样例:

4
1 3 6 9

输出样例:

117

解题

方法一:数学

思路

a1×a2+a1×a3++a1×an1+a1×an+a2×a3++a2×an1+a2×an+an2×an1+an1×an+an1×an=a1(a2+a3+...+an1+an)+a2(a3+...+an1+an)+an2(an1+an)+an1ana_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 \\

a1×a2+a1×a3++a1×an1+a1×an=i=1n(ai×(j=1najai))2a_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);
    }
}

0

评论区