一个序列的 宽度 定义为该序列中最大元素和最小元素的差值。
给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。由于答案可能非常大，请返回对 109 + 7 取余 后的结果。
子序列 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，[3,6,2,7] 就是数组 [0,3,1,6,2,2,7] 的一个子序列。
示例 1：
输入：nums = [2,1,3]
输出：6
解释：子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。
相应的宽度是 0, 0, 0, 1, 1, 2, 2 。
宽度之和是 6 。
示例 2：
输入：nums = [2]
输出：0
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-subsequence-widths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
const int MOD = 1e9 + 7;
public:
int sumSubseqWidths(vector<int> &nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), pow2[n];
pow2[0] = 1;
for (int i = 1; i < n; ++i)
pow2[i] = pow2[i - 1] * 2 % MOD; // 预处理 2 的幂次
long ans = 0L;
for (int i = 0; i < n; ++i)
ans += long(pow2[i] - pow2[n - 1 - i]) * nums[i]; // 在题目的数据范围下，这不会溢出
return (ans % MOD + MOD) % MOD; // 注意上面有减法，ans 可能为负数
}
};
【C++】数学（乘法）
- 假如数组：[2,1,3],因为子序列顺序不会对结果产生影响
- 比如它的子序列[1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 跟[1,2,3]的子序列[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]最终结果是一样的
- 所以我们按照递增排序后讨论，这样每个元素都比它左边大或相等(作为最大值)，比它右边小(作为最小值)
- 那么我们只需要讨论每个元素左右的贡献值，我们不妨拿数字2作为例子，那么它作为最大值贡献了2^i次(i=1,排序后)，作为最小值贡献了2^(n-i-1)次,可以用数学归纳证明(这里略)，注：贡献都包含本身统计，结果相减没影响
- 结果就是每个数贡献值相加sum(2^i-2^(n-i-1))*nums[i])