class Solution {
public:
int sumOfPower(vector<int>& nums) {
}
};
6423. 英雄的力量
给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：
i0 ，i1 ，... ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。
示例 1：
输入：nums = [2,1,4] 输出：141 解释： 第 1 组：[2] 的力量为 22 * 2 = 8 。 第 2 组：[1] 的力量为 12 * 1 = 1 。 第 3 组：[4] 的力量为 42 * 4 = 64 。 第 4 组：[2,1] 的力量为 22 * 1 = 4 。 第 5 组：[2,4] 的力量为 42 * 2 = 32 。 第 6 组：[1,4] 的力量为 42 * 1 = 16 。 第 7 组：[2,1,4] 的力量为 42 * 1 = 16 。 所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。
示例 2：
输入：nums = [1,1,1] 输出：7 解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 80 ms, 内存消耗: 9.6 MB, 提交时间: 2023-05-14 17:15:59
func sumOfPower(nums []int) (ans int) {
const mod int = 1e9 + 7
sort.Ints(nums)
s := 0
for _, x := range nums {
ans = (ans + x*x%mod*(x+s)) % mod // 中间模一次防止溢出
s = (s*2 + x) % mod
}
return
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 90.8 MB, 提交时间: 2023-05-14 17:15:38
class Solution {
public:
int sumOfPower(vector<int> &nums) {
const int MOD = 1e9 + 7;
sort(nums.begin(), nums.end());
int ans = 0, s = 0;
for (long long x: nums) {
ans = (ans + x * x % MOD * (x + s)) % MOD; // 中间模一次防止溢出
s = (s * 2 + x) % MOD;
}
return ans;
}
};
java 解法, 执行用时: 13 ms, 内存消耗: 52.6 MB, 提交时间: 2023-05-14 17:15:26
class Solution {
public int sumOfPower(int[] nums) {
final long MOD = (long) 1e9 + 7;
Arrays.sort(nums);
long ans = 0, s = 0;
for (long x : nums) {
ans = (ans + x * x % MOD * (x + s)) % MOD; // 中间模一次防止溢出
s = (s * 2 + x) % MOD;
}
return (int) ans;
}
}
python3 解法, 执行用时: 144 ms, 内存消耗: 26 MB, 提交时间: 2023-05-14 17:15:12
class Solution:
def sumOfPower(self, nums: List[int]) -> int:
MOD = 10 ** 9 + 7
nums.sort()
ans = s = 0
for x in nums:
ans = (ans + x * x * (x + s)) % MOD
s = (s * 2 + x) % MOD
return ans