题解 P2415 【集合求和】
Lhc_fl
·
2018-12-15 00:38:48
·
题解
此题坑点:
题目描述
给定一个集合s（集合元素数量<=30），求出此集合所有子集元素之和。
分析
我们来看一个例子：
\{1,2,3\}
可以得到，它的所有非空子集为
\{1,2,3\}$ $\{1,2\}$ $\{2,3\}$ $\{1,3\}$ $\{1\}$ $\{2\}$ $\{3\}
现在来分析每一个元素在每一个子集中出现的个数：
我们猜测：对于一个有限集合$A$，它的每一个元素在$A$的所有子集中出现的个数是${2^{\operatorname{card}(A)-1}}
证明： (集合论纯自学，可能格式有误, 请别在意QAQ)
设B\subseteq A , 记n=\operatorname{card}(A) ， s 为A 中所有元素之和
当\operatorname{card}(B)=1 时，显然，每个元素在B 中出现1 次；
当\operatorname{card}(B)=2 时，保证一个元素必选，在剩余的n-1 个元素中选择1 个元素，共C^1_{n-1}=n-1 种情况，故每个元素在B 中出现C^1_{n-1}=n-1 次；
当\operatorname{card}(B)=3 时，保证一个元素必选，在剩余的n-1 个元素中选择2 个元素，共C^2_{n-1}=\frac{(n-1)!}{2(n-1-2)!}=\frac{(n-1)(n-2)}{2} 种情况，故每个元素在B 中出现共C^2_{n-1}=\frac{(n-1)(n-2)}{2} 次；
当\operatorname{card}(B)=k 时，保证一个元素必选，在剩余的n-1 个元素中选择k-1 个元素，共C^{k-1}_{n-1} 种情况，故每个元素在B 中出现共C^{k-1}_{n-1} 次；
那么，每个元素在A 的每一个子集中出现的个数为：
$A$的所有子集元素之和为$s\times2^{n-1}
故代码如下：
#include<bits/stdc++.h>
using namespace std;
int main(){
long long tmp,num=0,sum=0;
while(cin>>tmp){sum+=tmp;num++;}//读入集合元素个数num和元素和sum
cout<<(long long)(sum*pow(2,num-1));//必须显式地转换为long long输出
return 0;
}①:
像我这样不懂为什么\sum\limits_{i=1}^{n}C^{i-1}_{n-1}=2^{n-1} 的可以看一下数学归纳法证明：
将用到的性质公式：
C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}
C^n_n=C^0_n=1
\sum\limits_{i=0}^{n}C^{i}_{n}=2^{n}
证明：
1)当n=1 时：
\sum\limits_{i=0}^{n}C^{i}_{n}=C^0_1+C^1_1=2=2^1
等式成立。
2)假设当n=k(k\in N_+) 时\sum\limits_{i=0}^{n}C^{i}_{n}=2^{n}
成立, 即\sum\limits_{i=0}^{k}C^{i}_{k}=2^{k}
那么当n=k+1 时:
\text{\ \ \ \ }$ $\sum\limits_{i=0}^{k+1}C^{i}_{k+1}
=C^{0}_{k+1}+C^{1}_{k+1}+C^{2}_{k+1}+...+C^{k}_{k+1}+C^{k+1}_{k+1}
=C^{0}_{k+1}+(C^{0}_{k}+C^{1}_{k})+(C^{1}_{k}+C^{2}_{k})+...+(C^{k-1}_{k}+C^{k}_{k})+C^{k+1}_{k+1}
=C^{0}_{k}+(C^{0}_{k}+C^{1}_{k})+(C^{1}_{k}+C^{2}_{k})+...+(C^{k-1}_{k}+C^{k}_{k})+C^{k}_{k}
=2(C^0_k+C^1_k+C^2_k+...+C^k_k)
=2\sum\limits_{i=0}^{k}C^{i}_{k}
=2\times2^k
=2^{k+1}
此时等式依然成立。假设成立。
故\sum\limits_{i=0}^{n}C^{i}_{n}=2^{n}
由此可以得到，\sum\limits_{i=1}^{n}C^{i-1}_{n-1}=2^{n-1}