子集的积和

这些是基本对称多项式。您可以像Wikipedia一样使用求和符号来编写它们。您还可以使用Vieta的公式一次获取所有多项式作为多项式的系数（最多为符号）

(x-a_1)(x-a_2)...(x-a_k) =   x^k -   (a_1 + ... + a_k) x^(k-1) +   (a_1 a_2 + a_1 a_3 + ... + a_(k-1) a_k)) x^(k-2) +   ... +   (-1)^k a_1 ... a_k

通过扩展（x-a_1）（x-a_2）…（x-a_k），您可以获得多项式时间算法来计算所有这些数字（您的原始实现以指数时间运行）。

编辑：Python实现：

from itertools import izip, chainl = [2,3,4]x = [1]    for i in l:    x = [a + b*i for a,b in izip(chain([0],x), chain(x,[0]))]print x

这给您[24，26，9，1]，因为2 * 3 * 4 = 24、2 * 3 + 2 * 4 + 3 * 4 = 26、2 + 3 + 4 =
9。最后1是空积，在您的实现中对应于k = 0。

这应该是O（N 2）。使用多项式FFT可以执行O（N log 2 N），但是我懒得编写该代码。