问题描述
2681. 英雄的力量 (Hard)
给你一个下标从 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)$ 时间内计算出结果，注意取模防止溢出！。
代码
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;
}
};