14042: 【原4042】面包要约会

题目描述

author: MW 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4042

Description

面包决定要移民缅甸。他一到达目的地就开始进行黑客活动。目前，他一共黑掉了它所住街区中的n台电脑，而这些电脑又恰好在一条直线上。

现在用序号\(1-n\)来表示面包黑掉的电脑，其中第i台电脑位于坐标\(x_i\)处，且每台电脑的坐标都不相同。

面包决定在繁重的工作后休息一下。因此他邀请他的小姐姐到一家餐馆吃饭。但是小姐姐说她愿意去，但是有一个条件：面包必须解决一个简单的任务

首先,\(A\)是所有被面包黑掉的电脑构成的集合，函数\(F(a) = \max_{i,j \in a} |x_i-x_j|\) , 其中\(a\)是\(A\)的一个非空子集。小姐姐让面包计算这样一个和式 \(\sum_{a\subseteq A, a\not= \phi}F(a)\)，由于结果非常大，小姐姐让面包对结果模1e9+7

然而，面包实在是太累了，他没办法完成这个任务，请你来帮助他成功参加约会吧。

Input Format

第一行，有一个整数n(\(1\leq n\leq 3e5\)), 表示被黑的电脑数目

第二行，有n个整数\(x_1,x_2,\cdots ,x_n(1\leq x_i \leq 1e9)\) 代表被黑电脑的坐标，并保证所有\(x_i\)不同。

Output Format

一个整数——要求模1e9+7

Sample Input 1

2
4 7

Sample Output 1

Sample Input 2

3
4 3 1

Sample Output 2

样例解释

在样例2中，一共有7个非空子集。其中只有\(\{4,3\},\{4,1\},\{3,1\},\{4,3,1\}\)会使结果增加。最后的结果为\((4-3)+(4-1)+(3-1)+(4-1)=9\)

Limits

对于50%的数据，\(1\leq n \leq 20\)

对于100%的数据，\(1\leq n\leq 3e5\)

其中\(1\leq x_i \leq 1e9\)

FineArtz's solution

/* 面包要约会 */
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

constexpr int MAXN = 3e5 + 5, MOD = 1e9 + 7;
int n;
long long x[MAXN];

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i];
    sort(x + 1, x + n + 1);
    long long ans = 0, doub = 1, sum = 0;
    for (int i = 2; i <= n; ++i){
        sum = sum * 2 % MOD;
        sum = (sum + x[i - 1]) % MOD;
        doub = doub * 2 % MOD;
        ans = (ans + (doub - 1) * x[i] - sum) % MOD;
    }
    cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

constexpr long long mod = (long long)(1e9 + 7);

int pos[300009] = { 0 };

template <class T, class T_val = decltype(*declval<T>()),
    class Compare = bool (*)(T_val, T_val)>
    void quick_sort(T start, T end,
        Compare cmp = [](T_val a, T_val b) {return a < b; }) {
    if (start == end)
        return;
    auto i = start, j = end;
    --j;
    if (i == j)
        return;
    //交换
    auto key = *start;
    for (bool status = true; i != j;) {
        if (status) {
            if (cmp(*j, key)) {
                *i = *j;
                ++i;
                status = false;
            }
            else
                --j;
        }
        else {
            if (cmp(key, *i)) {
                *j = *i;
                --j;
                status = true;
            }
            else
                ++i;
        }
    }
    *i = key;
    //递归
    quick_sort(start, ++i, cmp);
    quick_sort(i, end, cmp);
}


int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i)
        scanf("%d", &pos[i]);

    quick_sort(pos, pos + n);

    long long ans = 0, cur_ans = 0, cnt = 0;

    for (int i = 1; i < n; ++i) {
        cnt = (cnt * 2 + 1) % mod;
        cur_ans = (cur_ans * 2 + (pos[i] - pos[i - 1]) * cnt) % mod;
        ans = (ans + cur_ans) % mod;
    }

    cout << ans;

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const long long M = 1e9 + 7;
inline long long fast_expr(long long a, long long b) {
    long long sum = 1;
    while (b > 0) {
        if (b & 1) sum = (sum * a) % M;
        b >>= 1;
        a = (a * a) % M;
    }
    return sum;
}
int main() {
    int n;
    int pos[300000];
    long long sum = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &pos[i]);
    sort(pos, pos + n);
    for (int i = 0; i < n; i++) {
        long long addend = fast_expr(2, i) - fast_expr(2, n - i - 1);
        sum = (sum + (addend * pos[i] % M)) % M;
    }
    sum = (sum + M) % M;
    cout << sum << endl;
    return 0;
}