洛谷P2415 集合求和
2018-06-17 21:43:57来源:未知 阅读 ()
题目描述
给定一个集合s(集合元素数量<=30),求出此集合所有子集元素之和。
输入输出格式
输入格式:
集合中的元素(元素<=1000)
输出格式:
和
输入输出样例
2 3
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}}∑i=1n?Cn−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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:洛谷P1720 月落乌啼算钱
- 洛谷P1164->小A点菜 2020-05-18
- STL之set 2020-04-28
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash