小红的数组权值

[题目链接](https://www.nowcoder.com/practice/7bcd78aec6e74ebf9061245e5936c18d)

思路

题意

定义长度为 $k$ 的数组 $[b_1, b_2, \ldots, b_k]$ 的权值为 $\sum_{i=1}^{k} i \cdot b_i$ 。给定长度为 $n$ 的数组 $a$ ，求所有连续子数组的权值之和，对 $10^9+7$ 取模。

贡献法

暴力枚举所有子数组再逐个计算权值是 $O(n^3)$ 的，无法通过。我们换一个角度：考虑每个元素 $a[j]$ （ $0$ 索引）对最终答案的总贡献。

对于子数组 $a[l \ldots r]$ （ $0 \leq l \leq j \leq r \leq n-1$ ），元素 $a[j]$ 在该子数组中的下标为 $j - l$ （从 $0$ 开始），因此它的贡献系数为 $j - l + 1$ 。

所以 $a[j]$ 对答案的总贡献为：

$ $a[j] \cdot \sum_{l=0}^{j} \sum_{r=j}^{n-1} (j - l + 1)$ $

注意到 $r$ 不出现在 $(j - l + 1)$ 中，内层对 $r$ 求和直接变为乘以 $(n - j)$ ：

$ $a[j] \cdot (n - j) \cdot \sum_{l=0}^{j} (j - l + 1) = a[j] \cdot (n - j) \cdot \sum_{m=1}^{j+1} m = a[j] \cdot (n - j) \cdot \frac{(j+1)(j+2)}{2}$ $

因此答案为：

$ $\mathrm{ans} = \sum_{j=0}^{n-1} a[j] \cdot (n - j) \cdot \frac{(j+1)(j+2)}{2}$ $

样例验证

数组 $[1, 2, 3]$ ， $n = 3$ ：

$j$	$a[j]$	$n-j$	$(j+1)(j+2)/2$	贡献
0	1	3	1	3
1	2	2	3	12
2	3	1	6	18

总和 $= 3 + 12 + 18 = 33$ ，与样例一致。

取模处理

由于除以 $2$ 在模运算下不能直接做整除，需要乘以 $2$ 的模逆元。因为 $10^9 + 7$ 是奇数， $2$ 的逆元为 $\frac{10^9 + 8}{2} = 500000004$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    const long long MOD = 1000000007;
    const long long inv2 = (MOD + 1) / 2;
    long long ans = 0;
    for (int j = 0; j < n; j++) {
        long long a;
        scanf("%lld", &a);
        a %= MOD;
        long long coeff = (1LL * (n - j) % MOD) * ((1LL * (j + 1) % MOD * ((j + 2) % MOD)) % MOD) % MOD;
        coeff = coeff % MOD * inv2 % MOD;
        ans = (ans + a % MOD * coeff % MOD) % MOD;
    }
    printf("%lld\n", (ans % MOD + MOD) % MOD);
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long MOD = 1000000007L;
        long inv2 = (MOD + 1) / 2;
        long ans = 0;
        for (int j = 0; j < n; j++) {
            long a = sc.nextLong();
            a %= MOD;
            if (a < 0) a += MOD;
            long nj = (n - j) % MOD;
            long j1 = (j + 1L) % MOD;
            long j2 = (j + 2L) % MOD;
            long coeff = nj % MOD * (j1 % MOD * (j2 % MOD) % MOD) % MOD;
            coeff = coeff % MOD * inv2 % MOD;
            ans = (ans + a * coeff % MOD) % MOD;
        }
        System.out.println((ans % MOD + MOD) % MOD);
    }
}

复杂度

时间复杂度： $O(n)$ ，只需遍历数组一次。
空间复杂度： $O(1)$ ，只用了常数个变量。