题解 | #小红的数组权值#

题目链接

小红的数组权值

题目描述

小红定义一个长度为 $n$ 的数组的权值为 $\sum_{i=1}^{n} i \cdot a_i$ 。现在小红有一个长度为 $n$ 的数组，她想知道所有子数组的权值和是多少？答案对 $10^9+7$ 取模。

输入:

第一行输入一个整数 $n$ 。
第二行输入 $n$ 个整数。

输出:

输出一个非负整数，表示答案对 $10^9+7$ 取模的结果。

解题思路

这道题目的关键是理解数组权值的定义和所有子数组的概念。

一个长度为 $n$ 的数组的权值被定义为 $\sum_{i=1}^{n} i \cdot a_i$ ，即每个元素乘以它在数组中的位置（从 $1$ 开始计数）后的总和。
为了高效解决这个问题，我们需要数学推导来避免暴力枚举所有子数组。
考虑原数组中位置 $i$ 的元素 $a_i$ （下标从 $0$ 开始）对最终结果的贡献：
- 对于任何包含 $a_i$ 的子数组 $[j...k]$ （其中 $j \leq i \leq k$ ）， $a_i$ 在这个子数组中的位置是 $i-j+1$ 。
- 子数组的起点 $j$ 可以是 $0$ 到 $i$ ，共 $i+1$ 种可能。
- 子数组的终点 $k$ 可以是 $i$ 到 $n-1$ ，共 $n-i$ 种可能。
因此， $a_i$ 在所有子数组中的权值贡献为： $a_i \cdot \sum_{j=0}^{i} \sum_{k=i}^{n-1} (i-j+1)$
简化这个表达式：
- $\sum_{k=i}^{n-1} 1 = n-i$
- $\sum_{j=0}^{i} (i-j+1) = \sum_{j'=1}^{i+1} j' = \frac{(i+1)(i+2)}{2}$
因此， $a_i$ 的总贡献为： $a_i \cdot (n-i) \cdot \frac{(i+1)(i+2)}{2}$
对所有元素的贡献求和，得到最终结果。

代码

c++
java
python

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    
    long long result = 0;
    
    // 遍历每个元素，计算其在所有子数组中的贡献
    for (int i = 0; i < n; ++i) {
        // 计算 i 在 0-indexed 下的贡献
        long long position_sum = (long long)(i + 1) * (i + 2) / 2;
        long long subarrays = (long long)(n - i);
        long long contribution = (position_sum * subarrays) % MOD;
        
        // 将当前元素对最终结果的贡献加入
        result = (result + ((long long)arr[i] * contribution) % MOD) % MOD;
    }
    
    cout << result << endl;
    
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MOD = (int)(1e9 + 7);
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        long result = 0;
        
        // 遍历每个元素，计算其在所有子数组中的贡献
        for (int i = 0; i < n; i++) {
            // 计算 i 在 0-indexed 下的贡献
            long positionSum = (long)(i + 1) * (i + 2) / 2;
            long subarrays = (long)(n - i);
            long contribution = (positionSum * subarrays) % MOD;
            
            // 将当前元素对最终结果的贡献加入
            result = (result + ((long)arr[i] * contribution) % MOD) % MOD;
        }
        
        System.out.println(result);
    }
}

def solve(arr, n):
    MOD = 10**9 + 7
    result = 0
    
    # 遍历每个元素，计算其在所有子数组中的贡献
    for i in range(n):
        # 计算 i 在 0-indexed 下的贡献
        position_sum = (i + 1) * (i + 2) // 2
        subarrays = n - i
        contribution = (position_sum * subarrays) % MOD
        
        # 将当前元素对最终结果的贡献加入
        result = (result + (arr[i] * contribution) % MOD) % MOD
    
    return result

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

算法及复杂度

算法：数学推导 + 线性遍历。
时间复杂度： $O(n)$ ，其中 $n$ 是数组长度。我们只需要遍历数组一次，对每个元素计算其贡献。
空间复杂度： $O(n)$ ，用于存储输入数组。

由于时间限制为 $1$ 秒，空间限制为 $256$ MB，而我们的算法时间复杂度为 $O(n)$ ，对于题目给定的约束条件（数组长度和元素大小）来说，这是一个高效的解法，完全可以在时限内完成计算。