题目
分析
如果我们遍历所有可能的集合，那么就超时了。对于一个有n个元素的集合来说，它所有的子集（包括空集和全集）的数量是\(2^n\)个——这样的指数级增长实在是太快了。
考虑在这\(2^n\)个子集，某个数要么在要么不在，只有某个元素在子集的时候，对最后的总和有贡献。那么一个数在所有\(2^n\)个子集中，出现（也就是贡献总和）的次数就是\(2^{n-1}\)次。
于是：\(2^{n-1}\times a_1+2^{n-1}\times a_2+ \dots+2^{n-1}\times a_n=2^{n-1}\times \sum_{i=1}^n a_i\)。
我们在输入各个数字的时候就可以先求和，然后直接乘以\(2^{n-1}\)就好了。
答案
注意这里求\(2^{n-1}\)时，用到了快速求幂，也就是左移的方式。
思考
一个有n个元素的集合，它所有的子集（包括空集和全集）的数量是\(2^n\)个。怎么证明呢？
方法1：选择法
对于这n个元素，每个元素（不论集合大小），在某个集合中都有两种可能：出现或者不出现。而这n个元素是互相独立的，所以最终的子集数是\(2^n\)个。
方法2：数学归纳法
如果集合为空（\(n=0\)），那么只有一个子集（也就是空集\(\emptyset\)）。\(2^0=1\)，公式是成立的。
假定对于\(n-1\)的情况，子集总数是\(2^{n-1}\)，那么当集合中有了\(n\)个元素后：
- 对于前\(n-1\)个元素构成的所有子集，这第\(n\)个元素可以不在其中，那么就是\(n-1\)个元素的所有子集总数：\(2^{n-1}\)。
- 如果要包含第\(n\)个元素，可以在这\(2^{n-1}\)个子集中加上这个元素即可。总数还是：
\(2^{n-1}\)。 - 加起来就是\(2^n\)个。
方法3：二进制表示法
子集与二进制的对应关系：
对于集合 \(S={a_1, a_2, \dots, a_n}\)，可以用一个长度为n的二进制数表示一个子集：
- 如果第
i位为1，表示元素\(a_i\)被包含在子集中。 - 如果第
i位为0，表示元素\(a_i\)不被包含在子集中。
而长度（位数）为n的二进制数表示的范围是\([0, 2^n-1]\)，因此总数是\(2^n\)。
结论：
每个二进制数唯一对应一个子集，因此子集的总数是 ( 2^n )。
QED