洛谷 P2415 集合求和【数学公式/模拟】

给定一个集合s（集合元素数量<=30），求出此集合所有子集元素之和。

输入输出格式

输入格式：

集合中的元素（元素<=1000）

输出格式：

和

输入输出样例

输入样例#1：

2 3

输出样例#1：

说明

子集为：

[] [2] [3] [2 3] 2+3+2+3=10

保证结果在10^18以内。

【分析】非常容易推导出，每个元素在集合中总共出现了2^(n-1)（n指集合中元素的个数）次，以样例为例：

可以很容易的发现每个元素在集合中都各出现了2^(2-1) = 2次。如此，我们得到一个公式：

设元素个数为n，所有元素之和为sum，自己之和为ans，则：

ans = sum * 2^(n-1)。

完整的数学证明不方便给出，大家只要记住此公式即可。

【代码】：

#include<bits/stdc++.h>

using namespace std;

long long sum,a,ans,cnt;

int main()

{

    while(cin>>a)

    {

        sum+=a;

        cnt++;

    }

    ans+=pow(,cnt-);

    cout<<ans*sum;

    return ;

}

巴特西

洛谷 P2415 集合求和【数学公式/模拟】

输入输出格式

输入输出样例

说明

ans = sum * 2^(n-1)。

最新文章

热门文章