题解 P2415 【集合求和】

· · 题解

我把这题的公式推导过程详细的说一下。

先选出指定的一个元素，加入子集；

首先，当子集里只有一个元素时，在其他剩余的元素中不能选出任何元素加入到子集中，所以对于每个元素来说，均有 C_{n-1}^0 次被选中。

当子集里有 2 个元素时，在其他剩余的元素中选出 1 个元素加入到子集中，所以对于每个元素来说，均有 C_{n-1}^1 次被选中。

当子集里有 3 个元素时，在其他剩余的元素中选出 2 个元素加入到子集中，所以对于每个元素来说，均有 C_{n-1}^2 次被选中。

当子集里有 i\ (i\leq n) 个元素时，在其他剩余的元素中选出 i-1 个元素加入到子集中，所以对于每个元素来说，均有 C_{n-1}^{i-1} 次被选中。

所以共有 \sum_{i=1}^{n} {C_{n-1}^{i-1}} 次被选中，即 2^{n-1} 次被选中。

也可以这样考虑：如果要选中 x，剩下的元素都可选可不选，所以总共有 2^{n-1} 种方法。

代码：

#include<iostream>
#include<cmath>
using namespace std;
int a[31],i=0,j;
long long s=0;
int main(){
    //cout<<s;
    while(cin>>a[i++]);//合写cin>>a[i];i++;
    for(j=0;j<i;j++){
        s+=a[j];
    }
    s*=pow(2,i-2);//注意，i-2!
    cout<<s;
    return 0;
}