洛谷 P2415 集合求和

发布时间：2024年01月18日

原文链接：洛谷 P2415 集合求和?

一、题目链接

集合求和 - 洛谷

妥妥的一道数学问题，把数学层面的问题解决了，代码很好写；

题意：给n个元素的集合，求出所有子集的元素的和。

二、题目分析

思考一下：对于所有长度为m的子集而言，任意一个元素出现的次数和是相等的，比如，m为1时（即子集长度为1），每个元素只出现一次；

因此可以分析任意一个元素在所有子集中出现的次数，假设集合{a1, a2, ..., an+1}有【n+1】个元素，分析如下：

子集大小为1的集合：假设必选a1, 那么因为子集大小只有1，所以其他【n】个元素选【0】个即可，即元素a1在子集大小为【1】的集合中，出现了C\binom{0}{n}次；

子集大小为2的集合：假设必选a1, 那么在剩余的【n】个元素中可以再选【1】个即可，即元素a1在子集大小为【2】的集合中，出现了C\binom{1}{n}次；

同理可以得出：

子集大小为m（m<=n+1）的集合：假设必选a1, 那么在剩余的【n】个元素中可以再选【m-1】个元素即可，即元素a1在子集大小为【m】的集合中，出现了C\binom{m-1}{n}次；

......

通过以上的推论，可以得出任意一个元素在所有子集中出现的次数为：

C\binom{0}{n} + C\binom{1}{n} + C\binom{2}{n} + ... + C\binom{n}{n}

这个答案等于多少呢？想想二项式公式：

(x+y)^{n} = C\binom{0}{n}x^{n}y^{0} + C\binom{1}{n}x^{n-1}y^{1} + C\binom{2}{n}x^{n-2}y^{2} + ... C\binom{n}{n}x^{0}y^{n}

这个公式大家应该很熟悉，令x=1且y=1，公式左边为2^{n}，公式右边为：

C\binom{0}{n} + C\binom{1}{n} + C\binom{2}{n} + ... + C\binom{n}{n}

因此可以得到：

C\binom{0}{n} + C\binom{1}{n} + C\binom{2}{n} + ... + C\binom{n}{n}=2^{n}

有了上面的推导就很方便了，可以知道大小为【n+1】的集合的所有子集中，每个元素出现的总次数和为2^{n}，那么类推集合大小为【n】的集合的所有子集中，每个元素出现的次数和为2^{n-1}，所以本题只需要求出所有元素的和，再乘以每个元素出现的次数2^{n-1}即可。

三、AC code

#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
/**
 * 本题由于最终答案在10^18，在long long 范围内且没有负数，因此统一开unsigned long long
 **/
ull n = 0, sum = 0, x;
int main(){
	while(cin >> x) {
		sum += x;   // sum为所有元素的和
		n++;   // 由于本题没有告诉元素个数，因此需要自己统计元素个数
	}
	ull t = 1;  // 这里先定义类型为ull的t等于1，而没有直接使用1<<(n-1)，也是考虑用ull, 而不是int，如果直接写1<<(n-1)，结果为int
	cout << sum * (t<<(n-1));  // t<<(n-1)等价于2^(n-1)次数，位运算更快一些。
	return 0;
}

文章来源:https://blog.csdn.net/zpf123456789zpf/article/details/135641734
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章