一个集合任意两个元素不相同，求任意子集的max-min之和。
任意两个元素不相同降低了本题的难度。
将集合排序，考虑枚举最大值和最小值i,j(下标)
那么贡献为\(\sum_i\sum_{j}(a_i-a_j)2^{j-i-1}\)
将i和j拆开就行了\(\sum_i\frac{1}{2^{i+1}}(a_i\sum_j2^j-\sum_{j}a_j2^j)\)
取两个前缀和即可。
集合统计 前缀和
发布时间 2023-03-22 21:13:14作者: chdy
一个集合任意两个元素不相同，求任意子集的max-min之和。
任意两个元素不相同降低了本题的难度。
将集合排序，考虑枚举最大值和最小值i,j(下标)
那么贡献为\(\sum_i\sum_{j}(a_i-a_j)2^{j-i-1}\)
将i和j拆开就行了\(\sum_i\frac{1}{2^{i+1}}(a_i\sum_j2^j-\sum_{j}a_j2^j)\)
取两个前缀和即可。