P2415. 集合求和

发表于 分类于 阅读次数： Waline： 本文字数： 172 阅读时长 ≈ 1 分钟

考点

  • 排列组合

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long sum = 0;
  int x, cnt = 0;
  while (cin >> x) {
    ++cnt;
    sum += x;
  }
  cout << sum * (1 << (cnt - 1));
  return 0;
}

思路

对于每个元素x来说，它对子集和的贡献为： \[ x\cdot \left( \underset{\text{只含自己}}{\left( \begin{array}{c} n-1\\ 0\\ \end{array} \right)}+\underset{\text{选}1\text{个匹配}}{\left( \begin{array}{c} n-1\\ 1\\ \end{array} \right)}+\underset{\text{选}2\text{个匹配}}{\left( \begin{array}{c} n-1\\ 2\\ \end{array} \right)}+\cdots +\underset{\text{选}n-1\text{个匹配}}{\left( \begin{array}{c} n-1\\ n-1\\ \end{array} \right)} \right) \] 显然可以变成： \[ x\cdot 2^{n-1} \] 那么最终的子集和就是： \[ 2^{n-1}\cdot \sum{\begin{array}{c} n\\ i=1\\ \end{array}x_i} \]