一道hihocoder的编程题

Question

题目如下

时间限制:20000ms
单点时限:1000ms
内存限制:256MB

描述

有n个怪物，第i个怪物的血量是ai，设这n个怪物组成的集合为T。

现在你有一个技能，发动一次需要花费一个金币，当技能发动后，所有存活的怪物的血量都会-1，当怪物血量降为0后视为被消灭。

特别的，如果这次发动的技能后有至少一只怪物死亡，你都将获得一个金币的奖励。

令f(S)为消灭集合S中的怪物总共需要付出几个金币，即花费的金币数量减去获得的奖励金币数量。

求∑S⊆T f(S)，答案对109+7取模。
输入

第一行一个正整数n。

第二行n个正整数ai，表示第i个怪物的血量。

1 ≤ n ≤ 105，1 ≤ ai ≤ 109
输出

输出一个非负整数，表示答案。
样例输入

2
1 2

样例输出

1

---

我理解的思路
付出的金币数量=技能的发动数量-奖励的金币数量。
技能的发动数量为：生命值最高的怪的生命值。
奖励的金币数量为：不同的生命值数量。
令g(S)表示集合S的生命值的最大值，h(S)表示集合S中不同生命值的数量，则f(S)=g(S)-h(S)。

我的疑惑
一个具体集合的金币数量的计算很简单，但是如何高效的枚举每个集合（每个集合怪物的最大生命值，以及小于最大生命值的怪物的构成）,并且进行计算

这张图片的第二点和第三点不太理解

最后我希望有具体可行的代码可以参考
附上题目链接链接

Answer 1

就是普通的排列组合，别想多了。

• 第二点：最大生命值为$w$，那么

  • $x$个生命值为$w$的里面至少要选一个：$2^x-1$
  • $y$个生命值小于$w$的有没有都行：$2^y$

• 第三点：包含生命值$w$，那么

  • $n-y$个生命值大于$w$的有没有都行：$2^{n-y}$
  • $y$个生命值小于$w$的有没有都行：$2^y$

至于它为什么$2^y$都要减$1$，想了一下，觉得意义不明。倒是$2^x$不减$1$肯定有问题。

Answer 2

把a1~an 按生命值分类 排序 得到k个集合 b1~bk
g(s)的和等于

gs = 0 
for bi in list<b> 
    w = b集合的生命值
    count = (2^len(bi)-1)*2^len(b1,...bi-1)
    // count代表最大生命值为w的所有集合的数量, 其中每个集合都需要 w 个金币
    gs += w * count

h(s)的和等于

hs = 0
for bi in list<b>
    w = b集合的生命值
    count = (2^len(bi)-1)*2^(len(b1,...bi-1)+len(bi+1,...bk))
    // count代表所有集合里包含生命值为w的集合的数量, 其中每个集合都会在杀死w时都会奖励 1 个金币
    hs += count