洛谷P2415 集合求和

2018-06-17 21:43:57来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

给定一个集合s(集合元素数量<=30),求出此集合所有子集元素之和。

输入输出格式

输入格式:

 

集合中的元素(元素<=1000)

 

输出格式:

 

 

输入输出样例

输入样例#1:
2 3
输出样例#1:
10

说明

子集为:

[] [2] [3] [2 3] 2+3+2+3=10

保证结果在10^18以内。

 

 

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

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

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

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<map>
 6 #define LL long long int 
 7 using namespace std;
 8 const LL MAXN=80000;
 9 inline void read(LL &n)
10 {
11     char c=getchar();n=0;bool flag=0;
12     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 LL a[MAXN];
16 int main()
17 {
18     LL n=0;
19     while(cin>>a[n++]);
20     LL sum=0;
21     for(LL i=0;i<n;i++)
22         sum+=a[i];
23     printf("%lld",(LL)sum*(LL)pow(2,n-2));
24     return 0;
25 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:线性同余同余方程组解法(excrt)

下一篇:洛谷P1720 月落乌啼算钱