【Nowcoder 1105A】集合统计 链接： 题目大意： 正文: 代码：
题目大意：
定义一个集合 (S) 的 (f) 函数为 (f(S)=max{a}-min{a}(ain S)) 给定一个集合 (S)，求该集合所有非空子集的 (f) 函数之和。对 (10^9+7) 取模。
正文:
先排序，然后贡献就为：
[egin{aligned}sum_{i=1}^{n}sum_{j=i}^{n}(a_j-a_i)2^{j-i-1}&=sum_{i=1}^{n}left(sum_{j=i}^{n}a_j2^{j-i-1}-sum_{j=i}^{n}a_i2^{j-i-1}
ight)\
sum_{i=1}^{n}left(sum_{j=i}^{n}a_j2^{j-i-1}-a_i(2^{n-i}-1)
ight)end{aligned}]
然后其中一个和式用前缀和维护即可。
代码：
const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n;
ll a[N], ans, b[N], c[N], inv[N];
int main()
{
n = Read();
b[0] = 1;
inv[0] = 1, inv[1] = 500000004;
for (int i = 1; i <= n; i++)
a[i] = Read();
sort (a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
b[i] = b[i - 1] * 2 % mod,
c[i] = (b[i] * a[i] % mod + c[i - 1]) % mod,
inv[i] = inv[i - 1] * inv[1] % mod;
for (int i = 1; i < n; i++)
{
ans = (ans + (c[n] - c[i] + mod) % mod * inv[i + 1] % mod) % mod;
ans = (ans - (b[n - i] - 1) * a[i] % mod + mod) % mod;
}
printf ("%lld
", ans);
return 0;
}