Codeforces Round #415 C. Do you want a date?

题目大意:给你一个非空数集,让你求他所有子集的最大值与最小值的和。

看到题目给你两秒钟,嗯,肯定不能暴力( _ _)ノ|
昨晚做这道题的时候想了半天,这东西肯定是有个啥规律的,不然肯定TLE啊。
自己在本子上写了几个例子,似乎发现了某种规律,那就是每个数字作为最大值的次数或是最小值的次数,与其在子集sort后的排序有关,得到了这一点,很快就能写出代码啦( ^ω^)

ps.虽然代码是写出来了,但是却犯了个巨严重的错误,我在读取a[i]的时候忘了加&啊啊啊啊啊啊啊啊,搞得我一行一行调试了半天才发现为啥一直RE

#include <bits/stdc++.h>
const int Max=500005;
#define mod 1000000000+7
using namespace std;
typedef long long ll;
ll cnt[Max];
ll a[Max];
ll sum=0;
int n;
int main()
{
    cnt[0]=1;
    for(int i=1;i<=400000;i++)
    {
        cnt[i]=cnt[i-1]*2;
        cnt[i]%=mod;
    }
    scanf("%d",&n);
    for(int i=0;i<n;i++)
       scanf("%lld",&a[i]);
    sort(a,a+n);
    for(int i=1;i<n;i++)
    {
        sum+=1LL*a[i]*(cnt[i]-1);//强制转化避免数据溢出;排序后从小到大每个数字有(p[i]-1)的机会成为子集中的最大值。
        sum%=mod;
    }
    for(int i=0;i<n-1;i++)//最后一个元素不可能为最小值,所以n-1
    {
        sum-=1LL*a[i]*(cnt[n-i-1]-1);//排序后从小到大每个数字有(p[n-i-1]-1)的机会成为子集中的最小值
        sum%=mod;
    }
    if(sum<0)//前面在取余求和的时候数据可能会炸掉,所以要加个mod再取余,或者是像这里写的一样取余以后再判断是否小于0
    {
           sum+=mod;
           sum%=mod;
    }
    printf("%lld\n",sum);
}