题目要求返回所有的非空英雄组的力量之和,换言之,只要枚举到的所有组即可,不用管顺序如何。
因此我们可以先对序列进行排序,一旦排序完成,那么max
和min
计算会变得非常简单。前i个数最大的一定是末端那个,最小的一定是起始那个。
现在假设a,b,c,d,e五个数(已经排序)。
如果现在令d为最大值:
- 令a为最小值,中间的b,c可以选也可以不选,所有一共有\(2^2\)种选法,可以产生贡献\(2^2(d^2\times a)\)。
- 令b为最小值,那么中间的c可以选也可以不选,一共有\(2\)种选法,可以产生贡献\(2(d^2\times b)\)。
- 令c为最小值,那么会产生贡献\(d^2\times c\)。
- 令d为最小值,可以产生贡献\(d^3\)。
令\(s=2^2a + 2b + c\),那么贡献就是\(d^3 + d\times s\)。
如果现在令e为最小值,上面的情况同理,但是s会变成\(2^3a + 2^2b + 2c + d\)。
所以答案实际上是可以递推的,每一次递推,s会变成上一次的结果乘以2,再加上当前最大值。而每一次的贡献都是当前最大值的三次方乘以s。
class Solution
{
public:
int sumOfPower(vector<int>& nums)
{
int n = nums.size();
constexpr int mod = 1000000007;
sort(nums.begin(), nums.end());
using LL = long long;
int res = 0, s = 0;
for (LL x : nums)
{
res = (res + x * x % mod * (x + s)) % mod;
s = (s * 2 + x) % mod;
}
return res;
}
};