英雄的力量

题目

6423. 英雄的力量

---

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

• i0 ，i1 ，… ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])^2 * min(nums[i0],nums[i1] ... nums[ik]) 。

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 10^9 + 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 <= 10^5
• 1 <= nums[i] <= 10^9

题解

方法一：

思路

由于是所有子序列的英雄力量之和，所以考虑排序。

排序后考虑第i个数为序列中的最大值的所有序列的英雄力量之和，记为$f_i$。

显然答案就是$\sum f_i$

现在看一个例子，找规律。

nums = [1,2,3,4,5]

对于$f_4$，我们以4为最大值，最小值可以是1、2、3或4。
当最小值为4时，贡献为$4^2\cdot4$；
当最小值为3时，贡献为$4^2\cdot3$；
当最小值为2时，贡献为$4^2\cdot3 \cdot2$，这里为什么要乘以2，是因为对于以2为最小值4为最大值的子序列有两个[2,4],[2,3,4]；
当最小值为1时，贡献为$4^2\cdot3 \cdot2^2$，2和3可选可不选共计4中；

我们设$p_i = a_02^i+a_12^{i-1}+\cdots+a_ii$，

$p_i$满足递推式$p_i = 2p_{i-1}+a_i$

而$f_i = i^2(p_{i-1}+i)$

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    int sumOfPower(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        ll ans = 0, p = 0;
        for (ll i:nums) {
            ans += i*i%MOD*(p+i)%MOD;
            ans %= MOD;
            p = (p*2%MOD+i)%MOD;
        }
        return ans;
    }
};