https://leetcode.com/problems/sum-of-subsequence-widths/
https://blog.csdn.net/XX_123_1_RJ/article/details/81913307
很显然，对这个序列排序是不影响结果的。求一个数列的子集，利用二进制的方法，大家一定不会陌生，因为每个元素就两个状态吗？取或者不取。这个题目也可以是二进制的思想，具体思路如下：
（1）先对原始序列排序（排序是不影响结果的哦，这个很好理解）
（2）现在单独分析一个排序后的元素A[i]，那么这个元素在所有子集中，有几次是被作为最大值的？又有几次是被作为最小值的？
（3）继续分析，很显然A[i]被作为最大值的次数为 2^i - 1次（这里i从0开始），如何理解？0 ~ i 的所有子集共有2^(i+1)种，又因为每一位又两种状态，所以取最后一位被选中的有 2^i种，再减去只取这一位的1种，所以最后只有2^i - 1 。
（4）继续分析，很显然A[i]被作为最小的次数为 2^(n - i - 1) - 1次（这里i从0开始，n为数列的长度），倒过来分析，此时的i为最低位。
def sumSubseqWidths(self, A):
n, res, mod = len(A), 0, 10**9 + 7
A.sort()
pow2 = [1]
for i in range(1, n): # 先把2的次方求好
pow2.append(pow2[-1] * 2 % mod)
for i, x in enumerate(A):
res += (pow2[i] - 1) * x # x 被作为最大值得 次数 应该加上
res -= (pow2[n-1-i] - 1) * x # x 被作为最小值得 次数 应该减去
res %= mod
return res
https://zxi.mytechroad.com/blog/math/leetcode-891-sum-of-subsequence-widths/
ans=∑i=0n−1Ai2i–Ai2n–i–1=∑i=0n−1(Ai–An−i−1)2i
https://www.cnblogs.com/seyjs/p/9509261.html
题目定义的子序列宽度是最大值和最小值的差，因此可以忽略中间值。首先对数组排序，对于数组中任意一个元素，都可以成为子序列中的最大值和最小值而存在。例如数组[1,2,3,4,5,6]，对于元素3来说，由左边[1,2]组成的所有子序列都可以以3为最大值的，而右边[4,5,6]组成的所有子序列都可以以3为最小值。根据排列组合的原理：[1,2]可以组成的子序列个数为C(2,1) + C(2,2) ，而[4,5,6]可以组成的子序列个数为C(3,1) + C(3,2) + C(3,3) ，同样根据组合计算定律，C(n,1) + C(n,2) + ...... + C(n,n) = 2^n - 1。因为以3为最大值是做被减数，以3为最小值是做减数，因此以3作为最大/最小值的所有子序列的和宽度和就是：(2 ^ 2 - 1)* 3 - (2 ^ 3-1)*3 。同理，也可以求出其他元素的宽度和，并最终求出总宽度和。根据组合的对称性，C(n,m) = C(n,n-m)，因此只需要遍历一半的数组长度即可
不如转而考虑每个元素会在多少个子序列里做最大值，在多少个子序列里做最小值
先将原数组排序（排序并不会影响结果）， 则，起始位置是 i, 结束位置是 j 的串的宽度一定是 A[j]-A[i]，中间可以有串，也可以没有串。代码如下：
for(int i = 0; i < A.size(); ++i)
{
for(int j = i+1; j < A.size(); ++j)
{
ans = (ans + (long long int)pow2[j-i-1]*(A[j]-A[i]))%1000000007;
}
}
复杂度 O(n^2), 会超时， 可以将中间的循环化简：
Counting sort
Given an array of integers
A, consider all non-empty subsequences of A.
For any sequence S, let the width of S be the difference between the maximum and minimum element of S.
Return the sum of the widths of all subsequences of A.
As the answer may be very large, return the answer modulo 10^9 + 7.
Example 1:
Input: [2,1,3] Output: 6 Explanation: Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3]. The corresponding widths are 0, 0, 0, 1, 1, 2, 2. The sum of these widths is 6.
- Time Complexity: , where is the length of
A. - Space Complexity: , the space used by
pow2. (We can improve this to space by calculating these powers on the fly.)
Let's try to count the number of subsequences with minimum
A[i] and maximum A[j].
Algorithm
We can sort the array as it doesn't change the answer. After sorting the array, this allows us to know that the number of subsequences with minimum
A[i] and maximum A[j] is . Hence, the desired answer is:
public int sumSubseqWidths(int[] A) {
int MOD = 1_000_000_007;
int N = A.length;
Arrays.sort(A);
long[] pow2 = new long[N];
pow2[0] = 1;
for (int i = 1; i < N; ++i)
pow2[i] = pow2[i - 1] * 2 % MOD;
long ans = 0;
for (int i = 0; i < N; ++i)
ans = (ans + (pow2[i] - pow2[N - 1 - i]) * A[i]) % MOD;
return (int) ans;
}
https://leetcode.com/problems/sum-of-subsequence-widths/discuss/161267/C++Java1-line-Python-Sort-and-One-Pass?page=2https://blog.csdn.net/XX_123_1_RJ/article/details/81913307
很显然，对这个序列排序是不影响结果的。求一个数列的子集，利用二进制的方法，大家一定不会陌生，因为每个元素就两个状态吗？取或者不取。这个题目也可以是二进制的思想，具体思路如下：
（1）先对原始序列排序（排序是不影响结果的哦，这个很好理解）
（2）现在单独分析一个排序后的元素A[i]，那么这个元素在所有子集中，有几次是被作为最大值的？又有几次是被作为最小值的？
（3）继续分析，很显然A[i]被作为最大值的次数为 2^i - 1次（这里i从0开始），如何理解？0 ~ i 的所有子集共有2^(i+1)种，又因为每一位又两种状态，所以取最后一位被选中的有 2^i种，再减去只取这一位的1种，所以最后只有2^i - 1 。
（4）继续分析，很显然A[i]被作为最小的次数为 2^(n - i - 1) - 1次（这里i从0开始，n为数列的长度），倒过来分析，此时的i为最低位。
def sumSubseqWidths(self, A):
n, res, mod = len(A), 0, 10**9 + 7
A.sort()
pow2 = [1]
for i in range(1, n): # 先把2的次方求好
pow2.append(pow2[-1] * 2 % mod)
for i, x in enumerate(A):
res += (pow2[i] - 1) * x # x 被作为最大值得 次数 应该加上
res -= (pow2[n-1-i] - 1) * x # x 被作为最小值得 次数 应该减去
res %= mod
return res
https://zxi.mytechroad.com/blog/math/leetcode-891-sum-of-subsequence-widths/
Sort the array, for A[i]:
- i numbers <= A[i]. A[i] is the upper bound of 2^i subsequences.
- n – i – 1 numbers >= A[i]. A[i] is the lower bound of 2^(n – i – 1) subsequences.
- A[i] contributes A[i] * 2^i – A[i] * 2^(n – i – 1) to the ans.
int sumSubseqWidths(vector<int>& A) {
constexpr long kMod = 1e9 + 7;
const int n = A.size();
sort(begin(A), end(A));
long ans = 0;
long p = 1;
for (int i = 0; i < n; ++i) {
ans = (ans + (A[i] - A[n - i - 1]) * p) % kMod;
p = (p << 1) % kMod;
}
return (ans + kMod) % kMod;
}
https://leetcode.com/problems/sum-of-subsequence-widths/discuss/161267/C%2B%2BJava1-line-Python-Sort-and-One-Pass
The order in initial arrays doesn't matter,
my first intuition is to sort the array.
my first intuition is to sort the array.
For
There are
so there are
we should do
A[i]:There are
i smaller numbers,so there are
2 ^ i sequences in which A[i] is maximum.we should do
res += A[i] * (2 ^ i)
There are
so there are
we should do
n - i - 1 bigger numbers,so there are
2 ^ (n - i - 1) sequences in which A[i] is minimum.we should do
res -= A[i] * 2 ^ (n - i - 1)
Time Complexity:
O(NlogN)
public int sumSubseqWidths(int[] A) {
Arrays.sort(A);
long c = 1, res = 0, mod = (long)1e9 + 7;
for (int i = 0; i < A.length; ++i, c = (c << 1) % mod)
res = (res + A[i] * c - A[A.length - i - 1] * c) % mod;
return (int)((res + mod) % mod);
}题目定义的子序列宽度是最大值和最小值的差，因此可以忽略中间值。首先对数组排序，对于数组中任意一个元素，都可以成为子序列中的最大值和最小值而存在。例如数组[1,2,3,4,5,6]，对于元素3来说，由左边[1,2]组成的所有子序列都可以以3为最大值的，而右边[4,5,6]组成的所有子序列都可以以3为最小值。根据排列组合的原理：[1,2]可以组成的子序列个数为C(2,1) + C(2,2) ，而[4,5,6]可以组成的子序列个数为C(3,1) + C(3,2) + C(3,3) ，同样根据组合计算定律，C(n,1) + C(n,2) + ...... + C(n,n) = 2^n - 1。因为以3为最大值是做被减数，以3为最小值是做减数，因此以3作为最大/最小值的所有子序列的和宽度和就是：(2 ^ 2 - 1)* 3 - (2 ^ 3-1)*3 。同理，也可以求出其他元素的宽度和，并最终求出总宽度和。根据组合的对称性，C(n,m) = C(n,n-m)，因此只需要遍历一半的数组长度即可
def sumSubseqWidths(self, A): """ :type A: List[int] :rtype: int """ A.sort() res = 0 l = 1 r = pow(2, len(A) - 1) for i in range(len(A)/2): res += l * A[i] res -= r * A[i] res += r * A[len(A)-i-1] res -= l * A[len(A) - i - 1] l *= 2 r /= 2 return res % (pow(10,9) + 7)https://zhanghuimeng.github.io/post/leetcode-891-sum-of-subsequence-widths/
不如转而考虑每个元素会在多少个子序列里做最大值，在多少个子序列里做最小值
对于子序列而言，顺序不是很重要，所以首先可以把数组排序。[1]（这真是一个珍贵的直觉。）这之后，对于元素
A[i]，有i个比它更小的元素，所以在2 ^ i个子序列中，它是最大的元素；有n - i - 1个比它更大的元素，所以在2 ^ (n - i - 1)个子序列中，它是最大的元素。所以，就A[i]而言，result += (2^i - 2^(n-i-1)) * A[i]。在实际求解过程中，为了避免重复求2的幂次，可以把上述代码按2的幂次进行拆分。[2]
之前我对重复元素的情况有些疑虑，但现在想来并不是必要的。在上述方法中，我们对每个子序列都恰好考虑了两遍：一遍是开头元素，一遍是结尾元素。即使子序列中存在重复的元素，也并不会影响其中的最大值和最小值的数值。
https://blog.csdn.net/yanglingwell/article/details/81836848先将原数组排序（排序并不会影响结果）， 则，起始位置是 i, 结束位置是 j 的串的宽度一定是 A[j]-A[i]，中间可以有串，也可以没有串。代码如下：
for(int i = 0; i < A.size(); ++i)
{
for(int j = i+1; j < A.size(); ++j)
{
ans = (ans + (long long int)pow2[j-i-1]*(A[j]-A[i]))%1000000007;
}
}
复杂度 O(n^2), 会超时， 可以将中间的循环化简：
Counting sort
int sumSubseqWidths(vector<int>& A) {
constexpr long kMod = 1e9 + 7;
const int n = A.size();
countingSort(A);
long ans = 0;
long p = 1;
for (int i = 0; i < n; ++i) {
ans = (ans + (A[i] - A[n - i - 1]) * p) % kMod;
p = (p << 1) % kMod;
}
return (ans + kMod) % kMod;
}
private:
void countingSort(vector<int>& A) {
int max_v = INT_MIN;
int min_v = INT_MAX;
for (int a : A) {
if (a > max_v) max_v = a;
if (a < min_v) min_v = a;
}
vector<int> c(max_v - min_v + 1);
for (int a : A)
++c[a - min_v];
int i = 0;
int j = 0;
while (i < c.size()) {
if (--c[i] >= 0)
A[j++] = i + min_v;
else
++i;
}
}
https://buptwc.com/2018/08/23/Leetcode-891-Sum-of-Subsequence-Widths/- 首先我们需要明确，题目所求的widths和数组的本身的顺序没有关系，所以排序不会影响最后的结果，其次如果子串长度为1则widths为0，所以可以不用考虑
- OK，对于[1,2,3,4]这个数组，我们从第二个数开始分析：
- dp[1] = dp[0] + (2-1)*1 (对于nums[1] = 2)
- dp[2] = dp[1] + (3-1)*2 + (3-2)*1 (对于nums[2] = 3)
- dp[3] = dp[2] + (4-1)*4 + (4-2)*2 + (4-3)*1 (对于nums[3] = 4)
- 相信这么一写你肯定已经初步看出规律了，但是如果按照这个规律不做任何处理依次累加的话复杂度仍然是O(n^2)，肯定是不过关的，我们这里再写一下通用的式子吧:
- 至此，递推式关系已出，显然dp[0] = 0, dp[1] = A[1]-A[0].
思路：
- 注意递推式中有一个2^(i+1)，因为这个i可以达到20000，所以我们必须先对所有2的次方进行预处理，也就是mod 1e9+7！(把这个作为全局变量，不要来一组数据又重新算一次
rec,mod,s = [],10**9+7,1 for i in range(20000): rec.append(s) s *= 2 s %= mod class Solution(object): def sumSubseqWidths(self, A): """ :type A: List[int] :rtype: int """ if len(A) < 2: return 0 A.sort() dp = [0] * len(A) dp[0],dp[1] = 0,A[1]-A[0] for i in range(2,len(dp)): dp[i] = (3*dp[i-1] - 2*dp[i-2] + (A[i]-A[i-1]) * (rec[i]-1)) % mod return dp[-1]
