rainboy的解析

§ 解析

这个题目用的是排列组合的相关知识,在高中高二下学期学习.

一个长度为nn的序列,共有多少个子集?

Cn0+Cn1+⋯+Cnn=∑i=0nCni=2n C_n^0+ C_n^1+ \cdots + C_n^n = \sum_{i=0}^n C_n^i = 2^n

那么这些子集中,第一人元素a1a_1,出现过多少次?这个问题显然等价于含有a1a_1的子集有多少个.

使用数学的化归思维:

  1. 从nn个元素里,把a1a_1拿走,剩余n−1n-1个元素
  2. 在剩余的n−1n-1个元素里,任意形成子集xix_i,显然有2n−12^{n-1}个
  3. 然后把拿走的a1a_1放到每个xix_i子集里,

这样就保证每个子集都有a1a_1里,所以得出含有a1a_1的元素共有2n−12^{n-1}个,同理aia_i元素在所有的子集中也出现了2n−12^{n-1}个

所以最终的答案为

ans=2n−1a1+2n−1a2+⋯+2n−1an=2n−1(a1+a2+⋯+an)=2n−1∑i=1nai \begin{aligned} ans &= 2^{n-1}a_1 + 2^{n-1}a_2 + \cdots + 2^{n-1}a_n \\ &= 2^{n-1}(a_1 +a_2 + \cdots + a^n) \\ &= 2^{n-1}\sum_{i=1}^na_i \end{aligned}
cpp
copy 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

        #include <iostream>
using namespace std;

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