【深基7.习6】集合求和

解题思路

设集合有 n 个元素，元素和为 sum。每个元素会出现在恰好 2^(n-1) 个子集中，所以答案为 sum×2^(n-1)。输入没有元素个数，读到文件结束。

正确性说明

固定一个元素必须选，其余 n-1 个元素各有选或不选两种状态，共 2^(n-1) 种；逐元素累加贡献即可。

易错点

不能把第一个数当 n；用 long long 保存总和；空集贡献为 0。

复杂度

时间 O(n)，空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long x, sum = 0;
    int n = 0;
    while (cin >> x) {
        sum += x;
        n++;
    }
    cout << (n ? sum * (1LL << (n - 1)) : 0) << "\n";
    return 0;
}