洛谷P2415 集合求和
洛谷P2415 集合求和
attack
发布于 2018-04-11 17:07:32
发布于 2018-04-11 17:07:32
代码可运行
运行总次数：0
代码可运行
题目描述
给定一个集合s（集合元素数量<=30），求出此集合所有子集元素之和。
输入输出格式
输入格式：
集合中的元素（元素<=1000）
输出格式：
和
输入输出样例
输入样例#1：
2 3输出样例#1：
10说明
子集为：
[] [2] [3] [2 3] 2+3+2+3=10
保证结果在10^18以内。
首先，当子集里只有一个元素时，在其他剩余的元素中不能选出任何元素加入到子集中，所以对于每个元素来说，均有C_{n-1}^0Cn−10次被选中。
当子集里有2个元素时，在其他剩余的元素中选出1个元素加入到子集中，所以对于每个元素来说，均有C_{n-1}^1Cn−11次被选中。
当子集里有3个元素时，在其他剩余的元素中选出2个元素加入到子集中，所以对于每个元素来说，均有C_{n-1}^2Cn−12次被选中。
当子集里有i(i\leqn)(i\leqn)个元素时，在其他剩余的元素中选出i-1个元素加入到子集中，所以对于每个元素来说，均有C_{n-1}^{i-1}Cn−1i−1次被选中。
所以共有\sum_{i=1}^{n} {C_{n-1}^{i-1}}∑=1nCn−1i−1次被选中，即2^{n-1}2n−1次被选中。
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 }本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017-10-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
