1、数学

因为我们需要求得是子序列的宽度之和，我们可以先确定不同宽度对应的子序列的个数，而后将其相加即可。我们可以首先在子序列中固定最大值和最小值，此时在剩余的n−2n-2n−2个数中我们可以依次选择0或1或2一直到n−2n-2n−2个，根据组合数公式：Cn0+Cn1+Cn2+⋯+Cnn=2nC_{n}^{0} +C_{n}^{1}+C_{n}^{2}+\cdots+C_{n}^{n}=2^n Cn0​+Cn1​+Cn2​+⋯+Cnn​=2n我们可以确定当前的宽度对应了2n−22^{n-2}2n−2个子序列。接着我们可以在子序列中固定第二个最大值和最小值，同理，此时在剩余的n−2n-2n−2个数中我们可以依次选择0或1或2一直到n−3n-3n−3个。依次类推固定了最小值的子序列共有(max−min)×2n−2+(max2−min)×2n−3+⋯+(min2−min)×21(max-min)\times2^{n-2}+(max2-min)\times2^{n-3}+\cdots+(min2-min)\times2^1(max−min)×2n−2+(max2−min)×2n−3+⋯+(min2−min)×21。我们可以按照以上规律依次求出每一个宽度对应的子序列数，我们最终将其相加后可以得到如下式子：(max−min)×2n−2+(max+max2−min2−min)×2n−3+⋯+(max+max2−min2−min)×21+(max−min)×20(max-min)\times2^{n-2}+(max+max2-min2-min)\times2^{n-3}+\cdots+(max+max2-min2-min)\times2^{1}+(max-min)\times2^{0}(max−min)×2n−2+(max+max2−min2−min)×2n−3+⋯+(max+max2−min2−min)×21+(max−min)×20。我们对上述式子求和即可。

class Solution {
public:long long mod = 1e9 + 7;long pow(long x, int n) {long res = 1L;for (; n; n /= 2) {if (n % 2) res = res * x % mod;x = x * x % mod;}return res;}int sumSubseqWidths(vector &nums) {int n = nums.size();long long res = 0, sum = 0;sort(nums.begin(), nums.end());for (int i = 0; i < n - 1; ++i) {sum += nums[n - 1 - i] - nums[i];res = (long long) (res + sum * pow(2L, i)) % mod;}return res;}
};