以上的給予所有子集查找總和的值設置

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