题解：贡献法计数+前缀和

考虑第$i$个元素对结果的贡献，选择第$i$个元素对结果的贡献 $b[i]*(b[i+1]*1+b[i+2]*2+...+b[k]*(k-i))$

如果是选择第$i+1$个元素，对结果的贡献为$b[i+1]*(b[i+2]*1+b[i+3]*2+...+b[k]*(k-i-1))$

右边的差值其实就是$b[i+1]+b[i+2]+...+b[k]$

因此可以预处理一个后缀和数组来去一遍遍历，一遍计算，当然，也可以不使用后缀和数组，维护两个变量即可

代码

C++

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const int mod = 1e9 + 7;
void solve()
{
	int n;
	cin >> n;
	vector<ll>a(n + 1);
	for (int i = 1; i <= n; i++)cin >> a[i];
	vector<ll>lst(n + 1, 0);
	lst[n] = a[n];
	for (int i = n - 1; i > 0; i--)
		lst[i] = lst[i + 1] + a[i];
	ll sum = 0;
	for (int i = 1; i <= n; i++)
		sum = (sum + 1ll * i * a[i]) % mod;
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		sum = (sum - lst[i] + mod) % mod;
		ans = (ans + a[i] * sum) % mod;
	}
	cout << ans << endl;
}
int main()
{
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
	return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] argv) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        final int mod = 1000000007;
        long[] preSum = new long[n];
        for (int i = 0; i < n; i++) {
            preSum[i] = i == 0 ? arr[0] : preSum[i-1]+arr[i];
        }
        long sum = 0;
        for (int i = n-1; i >= 0; i--) {
            sum += 1l * arr[i] * i;
            sum %= mod;
        }
        long res = 0;
        for (int i = 0; i < n; i++) {
            res += 1l * arr[i] * sum;
            res %= mod;
            sum -= preSum[n-1] - preSum[i];
            sum = (sum + mod) % mod;
        }
        System.out.println(res);

    }

}

Python

n = int(input())
arr = list(map(int, input().split()))

mod = 1000000007
preSum = [0] * n
for i in range(n):
    preSum[i] = arr[i] if i == 0 else preSum[i-1] + arr[i]

sum_val = 0
for i in range(n-1, -1, -1):
    sum_val += 1 * arr[i] * i
    sum_val %= mod

res = 0
for i in range(n):
    res += 1 * arr[i] * sum_val
    res %= mod
    sum_val -= preSum[n-1] - preSum[i]
    sum_val = (sum_val + mod) % mod

print(res)

题目描述

米小游有一天拿到了一个数组$a$，他用这个数组构造一个新数组$b$，其中$a_i$代表$b$数组中有$a_i$个$i$。例如，若$a=[2,3,1]$，那么$b=[1,1,2,2,2,3]$。 现在给定$a$数组，你需要帮米小游求出$b$数组中所有连续子数组的极差之和。由于答案可能过大，请对$10^9+7$取模。数组的极差指最大值减去最小值。

输入格式

第一行输入一个正整数$n$，代表$a$数组的元素数量

第二行输入$n$个正整数$a_i$，代表$a$数组的元素。

$1\le n\le 10^5$

$1 \le a_i\le 10^6$

输出格式

一个整数，代表数组中所有区间的极差之和，对$10^9+7$取模的值。

样例

输入

2
2 1

输出

2

说明

a=[2,1]时，b数组为[1,1,2]。

此时b数组共有6个连续子数组:

[1]的极差为0

[1]的极差为0

[2]的极差为0

[1,1]的极差为0

[1,2]的极差为1

[1,1,2]的极差为1

因此答案是0+0+0+0+1+1=2