2681. 英雄的力量

难度困难

给你一个下标从 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

# 贡献法

直接思路：要计算取出的最大值最小值，那就排好序后，依次枚举每个 $2$ 个元素，对于其他中间元素，可选可不选，共有 $2^i$ 种，这样是 $O(N^2)$

对于 $nums:[1,2,3,4,5]$

此时最大值为 $4$，$4$ 作为一个数的力量为 $4^3$

• 最小值为 $1$，最大值为 $4$，中间有 $2$ 个元素：$[2,3]$，其中每个元素选 / 不选，就是子序列，每一个都 $2$ 种情况，即 $2\times2=2^2$ 种情况
• 最小值为 $2$，最大值为 $4$，中间有 $1$ 个元素：$[3]$，其中每个元素选 / 不选，就是子序列，每一个都 $2$ 种情况，即 $2=2$ 种情况
• 最小值为 $3$，最大值为 $4$，中间有 $0$ 个元素，只有 $1$ 种情况。

归纳为：$1\times 2^2\times4^2\\2\times 2^1\times4^2\\3\times 2^0\times4^2$ $+\,4^3$

​ $= 4 ^2\times(1\times 2 ^ 2 + 2 \times 2^1 + 3\times2^0) +4^3= 4 ^2 \times v_4 + 4^3 = 4^2(v_4+4)$ （最小值的贡献 $v_4$）

当枚举到 $5$ 的时候，复用 $v_4$

归纳为：$1\times 2^3\times5^2\\2\times 2^2\times5^2\\3\times 2^1\times5^2\\4\times2^0\times5^2$ $+5^3$

​ $= 5 ^2\times(v_4 \times 2 + 4 \times 2^0) + 5^3 = 5^2((v_4\times 2 + 4)+5)$ （贡献值）

假设有 $f_1$ $f_2$ ... $f_i$ $f_{i+1}$ ... $f_n$, 求总数

对于$f_i$, 遍历$f_1$ ~ $f_{i-1}$, 求出贡献值 $c_i$；

对于$f_{i+1}$, 遍历$f_1$ ~ $f_i$, 求出贡献值 $c_{i+1}$；

此时 $ans_{i + 1} = f_{i+1} ^2 (c_{i+1}+f_{i+1})，c_{i + 1} = c_i \times 2 + f_i$

class Solution {

    int MOD = 1000000007;

    public int sumOfPower(int[] nums) {

        Arrays.sort(nums);

        long ans = 0;

        // 初始化贡献值 c 等于 0，

        long c = 0;

        for (long num : nums) {

            ans = (ans + num * num % MOD * (c + num)) % MOD;

            c = (c * 2 + num) % MOD;

        }

        return (int) ans;

    }

}