# LeetCode 891. 子序列宽度之和

## 题目描述

• 1 <= A.length <= 20000
• 1 <= A[i] <= 20000

## 解题思路

### 第一次尝试，DFS 超时。

``````class Solution {
constexpr static int64_t MOD = 1e9+7;
int64_t max_min(vector<int>& sub) {
if (sub.empty()) return 0;
int maxVal = sub[0];
int minVal = sub[0];
for (int x : sub) {
maxVal = max(maxVal, x);
minVal = min(minVal, x);
}
return (int64_t)maxVal - minVal;
}
void dfs(int64_t& res, vector<int>& nums, vector<int>& sub, int start) {
if (start >= nums.size()) {
res += max_min(sub);
res %= MOD;
return;
}
{
sub.push_back(nums[start]);
dfs(res, nums, sub, start + 1);
sub.pop_back();
}
{
dfs(res, nums, sub, start + 1);
}
}
public:
int sumSubseqWidths(vector<int>& nums) {
int64_t res = 0;
vector<int> sub;
dfs(res, nums, sub, 0);
return res % MOD;
}
}; // TLE
``````

### 第二次尝试，乘方计算，溢出。

``````class Solution {
constexpr static int64_t MOD = 1e9+7;
public:
int sumSubseqWidths(vector<int>& nums) {
int64_t res = 0;
size_t n = nums.size();
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
res += ((nums[j] - nums[i]) * (1LL << (j-i-1)));
res %= MOD;
}
}
return res;
}
};
``````

### 第三次尝试，避免溢出的乘方计算，超时。

``````class Solution {
constexpr static int64_t MOD = 1e9+7;
public:
int sumSubseqWidths(vector<int>& nums) {
int64_t res = 0;
size_t n = nums.size();
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
// res += ((nums[j] - nums[i]) * (1LL << (j-i-1)));
// res %= MOD;

// 避免溢出 // 1 <= n <= 20000, 1 <= nums[i] <= 20000
int64_t exp2 = 1;
int k = j-i-1;
while (k > 30) {
exp2 *= (1LL << 30);
exp2 %= MOD;
k -= 30;
}
exp2 *= (1LL << k);
exp2 %= MOD;
res += ((nums[j] - nums[i]) * exp2);
res %= MOD;
// 重复计算太多次，还是TLE
}
}
return res;
}
};
``````

### 第四次尝试，带记忆的、避免溢出的乘方计算，超时。

``````int64_t exp2s[20003];
bool inited = false;

class Solution {
constexpr static int64_t MOD = 1e9+7;
public:
int sumSubseqWidths(vector<int>& nums) {
if (!inited) {
memset(exp2s, -1, sizeof(exp2s));
inited = true;
}

int64_t res = 0;
size_t n = nums.size();
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
// res += ((nums[j] - nums[i]) * (1LL << (j-i-1)));
// res %= MOD;

if (exp2s[j-i-1] < 0) {
int64_t exp2 = 1;
int k = j-i-1;
while (k > 30) {
exp2 *= (1LL << 30);
exp2 %= MOD;
k -= 30;
}
exp2 *= (1LL << k);
exp2 %= MOD;

exp2s[j-i-1] = exp2;
}
res += ((nums[j] - nums[i]) * exp2s[j-i-1]);
res %= MOD;
}
}
return res;
}
};
``````

### 进一步减少计算，公式变形。

``````constexpr static int64_t MOD = 1e9+7;

int64_t exp2s[20003];
bool inited = false;
int64_t exp2(int k) {
if (!inited) {
memset(exp2s, -1, sizeof(exp2s));
inited = true;
}

if (exp2s[k] >= 0) {
return exp2s[k];
}
int64_t exp2 = 1;
int t = k;
while (t > 20) {
exp2 *= (1LL << 20);
exp2 %= MOD;
t -= 20;
}
exp2 *= (1LL << t);
exp2 %= MOD;

return exp2s[k] = exp2;
}

class Solution {
public:
int sumSubseqWidths(vector<int>& nums) {
int64_t res = 0;
size_t n = nums.size();
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
res += nums[i] * (exp2(i) - exp2(n-i-1));
res %= MOD;
}
return res;
}
};
``````

## 参考代码

``````constexpr static int64_t MOD = 1e9+7;

int64_t exp2s[100003];
bool inited = false;
int64_t exp2mod1e9_7(int k) {
if (!inited) {
inited = true;
int64_t exp2 = 1;
for (int i=0; i<100003; i++) {
exp2s[i] = exp2;
exp2 = (exp2 << 1) % MOD;
}
}

if (k < 100003) {
return exp2s[k];
}

int t = 100001;
int64_t exp2 = exp2s[t];
for (; t + 30 < k; t+=30) {
exp2 *= (1LL << 30) % MOD;
exp2 %= MOD;
}
exp2 *= (1LL << (k-t)) % MOD;
exp2 %= MOD;
return exp2;
}

class Solution {
public:
int sumSubseqWidths(vector<int>& nums) {
int64_t res = 0;
size_t n = nums.size();
sort(nums.begin(), nums.end());
for (int i=0; i<n; i++) {
res += nums[i] * (exp2mod1e9_7(i) - exp2mod1e9_7(n-i-1));
res %= MOD;
}
return res;
}
}; // AC
``````

[LeetCode 891.] 子序列宽度之和【hard】

(0)
(0)