题目描述
对一个数组,求其所有子集的极差之和。
思路
不要逐个考虑每个子集,直接考虑用到某个数的子集的个数。方便起见先排个序。
对最小的数k0来说,包含它的子集,其极差都含有-a1,而包含它的子集共有2^(N-1)个。
一般地,对ki来说,极差含有-ak的子集有2^(N-1-i)个;极差含ki的子集有2^i个。
时间复杂度
1.排序。复杂度O(NlogN)
2.对每个ki,求它被+/-的次数。复杂度O(N)。
python3 代码
T = int(input())
for C in range(T):
n = int(input())
k = list(map(int, input().split()))
k.sort()
result = 0
for i in range(n):
result += k[i] * (2**i - 2**(n-i-1))
print("Case #%d: %d"%(C+1, result%1000000007))