Link: 集合统计

Description:

定义一个集合S的f函数为f(S)=max{a}−min{a}(a∈S)
给定一个集合S，求该集合所有非空子集的f函数之和。对10^9+7取模。

输入描述:
第一行一个数n，表示|S|
第二行n个数表示集合中的元素。保证没有重复元素。
输出描述:
输出共1行，即该集合所有非空子集的f函数对10^9+7取模的和。
示例1
输入
4
1 5 2 7
输出
48

Problem solving:
这道题的意思就是给你一个集合，让你求这个集合中所有非空子集中的最大最小值的差之和。集合中元素个数最多为1e6个。
一开始想的是暴力，但是肯定不行（数据太大了。然后想到了找规律！对，就是找规律。然后我列出来了这样的规律。对这个集合中的元素排一下序，排序之后，每个值对最后答案的贡献不管正负肯定都是2^n-1(n=1,2,3,.....)。根据这个规律写肯定也能写出来。但是就在这时，学长告诉了我：
排序完第i个值对答案的贡献是a[i]*(2^i-2^(n-i-1))(i从0开始)。直接算一下就行了。
我们考虑第排序完第i位的值，这个值与它之前的任意个数组成的子集中他都是最大值，对答案的贡献为正，即a[i]*2^i，这个值与它之后的任意个数组成的子集中他都是最最小值，对答案的贡献为负，即a[i]*(-2^(n-i-1))。

这道题确实不难，但是这种思想真的是我现在所欠缺的！

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6 + 10;
ll       er[maxn], a[maxn];
const ll mod = 1e9 + 7;
int main()
{
    er[0] = 1, er[1] = 2;
    for (int i = 2; i <= 1e6; i++)
        er[i] = (2 * er[i - 1]) % mod;
    ll n, ans = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        ans += ((er[i] - er[n - i - 1] + mod) % mod * a[i] + mod) % mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}
赏