一道hihocoder的編程題

題目如下

時間限制:20000ms
單點時限:1000ms
內(nèi)存限制:256MB

描述

有n個怪物，第i個怪物的血量是ai，設(shè)這n個怪物組成的集合為T。

現(xiàn)在你有一個技能，發(fā)動一次需要花費一個金幣，當(dāng)技能發(fā)動后，所有存活的怪物的血量都會-1，當(dāng)怪物血量降為0后視為被消滅。

特別的，如果這次發(fā)動的技能后有至少一只怪物死亡，你都將獲得一個金幣的獎勵。

令f(S)為消滅集合S中的怪物總共需要付出幾個金幣，即花費的金幣數(shù)量減去獲得的獎勵金幣數(shù)量。

求∑S?T f(S)，答案對109+7取模。
輸入

第一行一個正整數(shù)n。

第二行n個正整數(shù)ai，表示第i個怪物的血量。

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

輸出一個非負(fù)整數(shù)，表示答案。
樣例輸入

2
1 2

樣例輸出

我理解的思路
付出的金幣數(shù)量=技能的發(fā)動數(shù)量-獎勵的金幣數(shù)量。
技能的發(fā)動數(shù)量為：生命值最高的怪的生命值。
獎勵的金幣數(shù)量為：不同的生命值數(shù)量。
令g(S)表示集合S的生命值的最大值，h(S)表示集合S中不同生命值的數(shù)量，則f(S)=g(S)-h(S)。

我的疑惑
一個具體集合的金幣數(shù)量的計算很簡單，但是如何高效的枚舉每個集合（每個集合怪物的最大生命值，以及小于最大生命值的怪物的構(gòu)成）,并且進(jìn)行計算

這張圖片的第二點和第三點不太理解

最后我希望有具體可行的代碼可以參考
附上題目鏈接鏈接

回答

編輯回答

扯機(jī)薄

就是普通的排列組合，別想多了。

第二點：最大生命值為$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$肯定有問題。

2018年4月18日 11:18

編輯回答

苦妄

把a(bǔ)1~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的所有集合的數(shù)量, 其中每個集合都需要 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的集合的數(shù)量, 其中每個集合都會在殺死w時都會獎勵 1 個金幣
    hs += count

2018年9月8日 00:55