Leetode-891-子序列宽度之和

1、数学

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

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<int> &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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24