贡献法

lc891

sort，预处理2的幂次

计算每个元素作为子序列最大/最小值的贡献差之和

ans += long(pow2[i] - pow2[n - 1 - i]) * nums[i];

最终取模得到所有子序列宽度的总和

class Solution {
public:
int sumSubseqWidths(vector<int>& nums) {
constexpr int MOD = 1'000'000'007;
ranges::sort(nums);
int n = nums.size();
vector<int> pow2(n);
pow2[0] = 1;
for (int i = 1; i < n; i++) {
pow2[i] = pow2[i - 1] * 2 % MOD; // 预处理 2 的幂次
}

long long ans = 0;
for (int i = 0; i < n; i++) {
ans += long(pow2[i] - pow2[n - 1 - i]) * nums[i];// 在题目的数据范围下，这不会溢出
}
return (ans % MOD + MOD) % MOD; // 注意上面有减法，ans 可能为负数
}
};

太妙了==最开始陷在计算每一对pair的贡献，一直跳不出On2的陷阱qwq