Нахождение значения суммы по всем подмножеств данного множества

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).

код Питон ниже работает пошагово, где 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