CodeChef – Set Difference [排序+递推]

点击打开vjudge题目链接

题意

给你一个集合,求出所有子集的最大最小值差的和。

分析

山理山科友谊赛的时候的题,应该是水题…不过没人做啊,最后比完也没读题,就是考虑每个数字对于最后答案的贡献就可以了。

Python3代码

base, mod = [1], 1000000007
for i in range(100005):
    base.append(base[-1] * 2 % mod)
for kase in range(int(input())):
    _, res, v = input(), 0, sorted([int(i) for i in input().split()])
    for i in range(len(v)):
        res = (res + v[i]*(base[i]-base[len(v)-i-1])) % mod
    print((res + mod) % mod)

欢迎留言