洛谷P2415 集合求和(数学问题,使用集合子集求和公式)

发布时间 2023-04-11 16:42:14作者: 凪风sama

可以知道对于一个有n个数据的集合,其子集个数有2^n个

至于证明可以这样理解,对于n个数据,其子集就是对数据进行组和,而对于每个位置上的数据,组合时仅有两种状态即有此数据或无此数据,也就是有两种可能,而对于n个数据,就有2^n种可能

不妨设其中一个非空数据X,对于X,依据X可以将子集划分为两种,包含X的子集和不包含X的子集,其个数分别都为2^(n-1),也就是说X在所有子集中出现了2^(n-1)次,同理对其他非空数据亦如此

所以所有子集中的所有元素的和即为(X1+X2+X3+X4+.........+Xn)*2^(n-1),这样就可以以较低复杂度解决此题