集合求和

题目描述

给定一个集合 $s$（集合元素数量 $\le 30$），求出此集合所有子集元素之和。

输入格式

集合中的元素（元素 $\le 1000$）

输出格式

$s$ 所有子集元素之和。

样例 #1

样例输入 #1

2 3

样例输出 #1

10

提示

【样例解释】

子集为： ∅ , { 2 } , { 3 } , { 2 , 3 } \varnothing, \{ 2 \}, \{ 3 \}, \{ 2, 3 \} ∅,{2},{3},{2,3}，和为 $2+3+2+3=10$。

---

【数据范围】

对于 $100\%$ 的数据，$1\le |s|\le 30$，$1\le s_i\le 1000$，$s$ 所有子集元素之和 $\le {10}^{18}$。

标签：集合论，数学，排列组合

知识点:

• 集合所有子集中的每个元素个数总和是相等的

• 集合所有子集之和=$sum\ast 2^{n-1}$(n代表元素的个数,sum是元素的和）

思路

我们先模拟一下，求集合所有子集之和的过程

以A= { 1 , 2 , 3 , 4 } \left\{1,2,3,4\right\} {1,2,3,4}为例

• $0元子集:$ $\varnothing$

• 1 元子集 : { 1 } 1元子集:\left\{1\right\} 1元子集:{1} { 2 } \left\{2\right\} {2} { 3 } \left\{3\right\} {3} { 4 } \left\{4\right\} {4}

• $2元子集$： { 1 , 2 } \left\{1,2\right\} {1,2} { 1 , 3 } \left\{1,3\right\} {1,3} { 1 , 4 } \left\{1,4\right\} {1,4} { 2 , 3 } \left\{2,3\right\} {2,3} { 2 , 4 } \left\{2,4\right\} {2,4} { 3 , 4 } \left\{3,4\right\} {3,4}

• $3元子集:$ { 1 , 2 , 3 } \left\{1,2,3\right\} {1,2,3} { 1 , 2 , 4 } \left\{1,2,4\right\} {1,2,4} { 1 , 3 , 4 } \left\{1,3,4\right\} {1,3,4} { 2 , 3 , 4 } \left\{2,3,4\right\} {2,3,4}

• $4元子集:$ { 1 , 2 , 3 , 4 } \left\{1,2,3,4\right\} {1,2,3,4}

我们仔细观察一下所有的集合，我们可以发现1出现的次数和2，3，4出现的次数是相等的，出现了八次

我们可以猜想在集合所有子集中每个元素出现次数为$2^{n-1}$次，集合A中所有元素之和为sum

$所有子集之和=$$sum\ast 2^{n-1}$​

下面是我朴素的推理过程，不保证对，发现不对之处还望指出，万分感谢！！！

ok,那就直接上代码了

#include<bits/stdc++.h>
#define int long long
int a[1005];
int ans,sum;
signed main()
{int s;while(scanf("%lld",&s)!=-1){if(a[s]==0){ans+=s;sum++;}}ans*=pow(2,sum-1);printf("%lld",ans);return 0;
}

我们下期再见！！！