洛谷题单指南-分治与倍增-P2415 集合求和

原题链接：https://www.luogu.com.cn/problem/P2415

题意解读：计算集合所有子集中元素之和。

解题思路：

集合的特性：互异性，元素各不相同

来看样例：2 3，可以组成的子集有

空

2

3

2 3

2和3都出现2次

再比如：1 2 3，可以组成的子集有

空

1

2

3

1 2 

1 3

2 3

1 2 3

1,2,3各出现4次

由于在集合中选0~n个元素，每个元素的机会都是均等的，可以断定所有子集中各元素出现次数一定相等。

对于n个元素的集合，所有子集中元素个数之和为：

C(n,0) * 0 + C(n,1) * 1 + C(n,2) * 2 + ... + C(n,n) * n = n * 2^(n-1)

以上等式是根据二项式定理推导出的恒等式，如果不了解，也可以直接对左边组合数求值，根据

C(n,m) = C(n-1,m) + C(n-1,m-1)进行递推求组合数即可

用子集元素个数除以n即得到每个数出现的次数：2^(n-1)

100分代码：

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

int main()
{
    int sum = 0, cnt = 0, x;
    while(cin >> x) sum += x, cnt++;
    long long ans = sum * pow(2, cnt - 1);
    cout << ans;
    return 0;
}