洛谷P2415题解

分析

题意：给定一个包含不超过 $30$ 个元素的集合，求所有子集的元素之和。例如，集合 ${2,3}$ 的所有子集为 $\varnothing, { 2 }, { 3 }, { 2, 3 }$，其元素和为 $2+3+2+3=10$。

通过观察可以发现，每个元素在所有子集中出现的次数是相同的。

对于一个大小为 $n$ 的集合，每个元素出现的次数为 $2^{n-1}$。例如，集合 ${2,3}$ 中，元素 $2$ 和 $3$ 各出现 $2$ 次 $2^{2-1}=2$。

所以所有子集的元素之和为 $\left( \sum_{i=1}^{n} a_i \right) \times 2^{n-1}$。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[30];
signed main() {
	int cnt = 0, sum = 0;
	while (cin >> a[cnt]) {
		sum += a[cnt];
		cnt++;
	}
	int mul = 1;
	for (int i = 1; i < cnt; i++) mul *= 2;
	cout << sum * mul;
	return 0;
}