891.子序列宽度之和

链接：891.子序列宽度之和
难度：Hard
标签：数组、数学、排序
简介：给你一个整数数组 nums ，返回 nums 的所有非空 子序列 的 宽度之和 。

题解 1 - cpp

• 编辑时间：2022-11-18
• 执行用时：224ms
• 内存消耗：52.5MB
• 编程语言：cpp
• 解法介绍：因为子序列是选取某几个元素组成所以和顺序无关，先排序然后比较对于每一个元素，有几次做最大值有几次做最小值。

class Solution {
public:
    typedef long long ll;
    const ll mod = 1e9 + 7;
    int sumSubseqWidths(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        ll ans = 0, n = nums.size();
        for (ll i = 0; i < n; i++) ans = (ans + (toCount(i + 1) - toCount(n - i)) * nums[i]) % mod;
        return ans;
    }
    ll toCount(ll num) {
        return quick_pow(2, num - 1);
    }
    ll quick_pow(ll a, ll b) {
        ll ans = 1, tmp = a;
        for (; b; b >>= 1) {
            if (b & 1) ans = (ans * tmp) % mod;
            tmp = (tmp * tmp) % mod;
        }
        return ans;
    }
};