问题描述
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;
}
};
标签:nums,Hard,times,num,英雄,力量,2681,mod
From: https://www.cnblogs.com/zwyyy456/p/17479221.html