以上的给予所有子集查找总和的值设置

Question

给定一个序列A={a1,a2,a3,…,an}我们必须找到长*的

总和（所有子产品）

For EX: 
A= {1 2} 
There are 3 sub sequences = {1} , {2} , {1,2} 
S = 1*(1) + 1*(2) + 2*(1*2) 
    = 1+2+4= 7 

Similarly for A={1,2,3} we have S=46. 

是否有有效的方法来计算这个数量，因为每个元素会出现2^n-1次？

Answer 1

是的，线性时间。

让

f(x) = (1 + a1*x) * (1 + a2*x) * … * (1 + an*x). 

我们有

 n 
f(x) = ∏ (1 + aj*x) 
     j=1 

    =  ∑   ∏ aj*x. 
     S ⊂ {1, …, n} j ∈ S 

让f'是f导数相对于x，

       |S|-1 
f'(x) =  ∑  |S| * x  * ∏ aj, 
     S ⊂ {1, …, n}    j ∈ S 

所以答案为f'(1)。下面

Python的代码工作增量，其中f是f(1)的值，并且是df的f'(1)值。 df的更新使用衍生产品的产品规则。

def answer(A): 
    f, df = (1, 0) 
    for a in A: 
     # multiply by (1 + a*x), at x=1 
     f, df = (f * (1 + a), df * (1 + a) + f * a) 
    return df