P2415集合求和 题解
P2415 集合求和
题解
公式推导：
设集合有 n 个元素，记为 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1,a2,…,an。
每个子集要么包含某个元素，要么不包含。
我们固定某个元素 a k a_k ak，再从剩下的 n − 1 n - 1 n−1 个元素中任选若干组成子集。
所以包含 a k a_k ak 的子集个数 = 从 n − 1 n - 1 n−1 个元素中选任意个数的方式总和：
∑ i = 0 n − 1 ( n − 1 i ) = 2 n − 1 \sum_{i=0}^{n-1} \binom{n-1}{i} = 2^{n-1} i=0∑n−1(in−1)=2n−1
即：每个元素在所有子集中恰好出现 2 n − 1 2^{n-1} 2n−1 次。
因此：
所有子集的元素和 = ( a 1 + a 2 + ⋯ + a n ) × 2 n − 1 \text{所有子集的元素和} = (a_1 + a_2 + \cdots + a_n) \times 2^{n-1} 所有子集的元素和=(a1+a2+⋯+an)×2n−1
代码
#include<bits/stdc++.h>
using namespace std;long long ans;int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);vector<int> arr;int x;while(cin>>x){arr.push_back(x);}for(int i:arr) ans+=i;ans*=pow(2,arr.size()-1);cout<<ans;return 0;
}