题解 | 小红的数组权值

import java.math.BigInteger;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        BigInteger s = BigInteger.ZERO;
        BigInteger ONE = BigInteger.ONE;
        BigInteger TWO = BigInteger.valueOf(2);
        BigInteger MOD = BigInteger.valueOf(1000000007L);
        for (int i = 0; i < n; i++) {
            BigInteger I = BigInteger.valueOf(i);
            BigInteger b = ((I.add(TWO).multiply(I.add(ONE))).multiply(BigInteger.valueOf(
                                n - i)).divide(TWO));
            int a = in.nextInt();
            s = s.add(b.multiply(BigInteger.valueOf(a)));
            s = s.mod(MOD);
        }
        System.out.println(s);
    }
}

n个数，子序列用首尾两个数的下标表示，如 (x,y) 表示从ax到ay

对于第i个数ai，它的权重为k的子序列有：(i-k+1,i)、(i-k+1,i+1)、(i-k+1,i+2)、……、(i-k+1,n-1)、(i-k+1,n)，一共(n-i+1)个，总共对最终的权值和贡献 k*(n-i+1)*ai

当 x<= i 时， (x,y) 包含 ai，也就是说，ai在子序列中的不同权重可以是 1、2、3、……、i-1、i，总计贡献：

(1+2+3+……+(i-1)+i)*(n-i+1) = i*(i+1)*(n-i+1)/2*ai

然后遍历每一个ai，求和即可。

使用Java的难点在于一般的int会溢出，需要大量使用BigInteger类，C++下则应该使用_int64以防止溢出