思路：公式变换

对于每个元素，考虑其贡献 假设下标从 00 开始 第$i$ 个元素为第1个的子数组数量为：$n-i$个 第 $i$ 个元素为第2个的子数组的数量为$n-(i-1)-1=n-i$个

第 $i$ 个元素为第3个的子数组的数量为$n-(i-2)-2=n-i$个

第 $i$个元素为第$j$个的子数组的数量为$n-(i-(j-1))-(j-1)=n-i$ 个

最多是有$(i+1)$个，即$j\le i+1$

第 $i$ 个元素的总贡献为：

$(n-i)\times 1\times b[i]+(n-i)\times 2\times b[i]+...+(n-i)\times (i+1)\times b[i]=(n-i)\times b[i]\times (i+2)\times (i+1)\times 2$

时间复杂度：$O(n)$

代码

C++

#include <iostream>
using namespace std;

int main()
{
    int mod = 1e9 + 7;

    int n;
    cin >> n;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;

        long long cnt = 1ll * (i + 1) * (i + 2) / 2 % mod;
        ans = (ans + 1ll * (n - i) * x % mod * cnt % mod) % mod;
    }

    cout << ans << "\n";

    return 0;
}

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        Solution3 s = new Solution3();
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int j = 0; j < n; j++) {
            arr[j] = sc.nextInt();
        }
        System.out.println(s.subWeightedSum(arr));
    }

}

class Solution3 {

    public static long mod = (long)1e9 + 7;

    public int subWeightedSum(int[] arr) {
        int n = arr.length;
        long cnt = 0;
        for(int i = 0; i < n; i++) {
            long curSum = (i + 1) * (long)(i + 2) / 2 % mod;
            cnt += arr[i]% mod * (n - i)% mod * curSum % mod;
            cnt = cnt % mod;
        }
        return (int)cnt;
    }
}

Python

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

mod = 10**9+7


res = 0
for i in range(n):
    l = i + 1
    r = n - i
    cnt = ((l + 1) * l // 2) * r % mod
    res = (res + cnt * w[i] % mod) % mod
print(res)

题目描述

小红有一个长度为 $n$ 的数组 $a$ ，下标从 $1$ 开始。

他对这个数组的权值定义为：$1\times a_1+2\times a_2 + 3\times a_3 + \cdots + n\times a_n$

现在小红想要问你，这个数组的所有连续子数组的权值之和是多少。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$，表示数组的长度。
第二行，$n$ 个整数，第 $i$ 个整数为 $a_i(1 \leq a_i \leq 10^9)$ 。

输出描述

一个非负整数，表示所有子数组的权值之和，答案对 $10^9+7$ 取模

样例

输入

3
1 2 3

输出

33

说明 对于子数组 $a[1]$ 来说，权值为 $1$
对于子数组 $a[2]$ 来说，权值为 $2$
对于子数组 $a[3]$ 来说，权值为 $3$
对于子数组 $a[1,2]$ 来说，权值为 $5$
对于子数组 $a[2,3]$ 来说，权值为 $8$
对于子数组 $a[1,2,3]$ 来说，权值为 $14$
总和为 $33$ 。