# 2681. 英雄的力量 (Hard)

## 问题描述
[2681. 英雄的力量 (Hard)](https://leetcode.cn/problems/power-of-heroes/)
给你一个下标从 **0** 开始的整数数组 `nums` ，它表示英雄的能
力值。如果我们选出一部分英雄，这组英雄的 **力量** 定义为：

- `i₀` ， `i₁` ，... `iₖ` 表示这组英雄在数组中的下标。那么这组英雄的力量为 `max(nums[i₀],nums[i₁] ... nums[iₖ])² * min(nums[i₀],nums[i₁] ... nums[iₖ])` 。

请你返回所有可能的 **非空** 英雄组的 **力量** 之和。由于答案
可能非常大，请你将结果对 `10⁹ + 7` **取余。**

**示例 1：**

```
输入：nums = [2,1,4]
输出：141
解释：
第 1 组：[2] 的力量为 2² * 2 = 8 。
第 2 组：[1] 的力量为 1² * 1 = 1 。
第 3 组：[4] 的力量为 4² * 4 = 64 。
第 4 组：[2,1] 的力量为 2² * 1 = 4 。
第 5 组：[2,4] 的力量为 4² * 2 = 32 。
第 6 组：[1,4] 的力量为 4² * 1 = 16 。
第 7 组：[2,1,4] 的力量为 4² * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 
。

```

**示例 2：**

```
输入：nums = [1,1,1]
输出：7
解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组
的力量之和为 7 。

```

**提示：**

- `1 <= nums.length <= 10⁵`
- `1 <= nums[i] <= 10⁹`

## 解题思路
首先，对数组相关的问题，我们要思考了能不能先对数组进行排序，由于这题是选择子序列，即可以不连续，因此数组的顺序对结果没有影响。

然后，我们可以采取**贡献法**的思路，即对每个元素，考虑它作为最大值时，对结果的贡献。

例如，考虑 $[1,\ 2,\ 3,\ 4,\ 5]$，$4$ 作为最大值时，对结果的贡献为 $4^2 \times(1 \times 2^2 + 2\times 2^1 + 3 \times 2^0 ) + 4^3$，记为 $a_3^2 s_3 + a_3^3$，$5$ 作为最大值时，对结果的贡献为 $5^2\times (1\times 2^3 + 2\times 2^2+ 3\times2^1 + 4) + 5^3$，记为 $a_4^2 s_4 + a_4^3$。

有 $s_i = 2 * s_{i - 1} + a_{i - 1}$。

因此，我们可以在 $O(1)$ 时间内计算出结果，注意取模防止溢出！。

## 代码
```cpp
class Solution {
  public:
    int sumOfPower(vector<int> &nums) {
        int mod = 1000000007;
        sort(nums.begin(), nums.end());
        long res = 0;
        long s = 0;
        int n = nums.size();
        for (long num : nums) {
            res = (res + ((num * num) % mod) * ((num + s) % mod)) % mod; // 防止溢出
            s = (2 * s + num) % mod;
        }
        return res;
    }
};
```