c++ - 大小为 K 的子集的乘积之和

Question

给定一个包含 n 个元素的集合，找到大小为 k(k 是另一个整数)的子集的乘积之和。

n 的范围是 1000s，所以我需要比指数时间复杂度更快的东西。

我觉得这个问题可以使用多项式 FFT 来解决，但我不确定。另外，检查一下 https://math.stackexchange.com/questions/786183/sum-of-multiplication-of-all-combination-of-m-element-from-an-array-of-n-element/788655#788655

例如:

小号:{1, 2, 3, 4, 5}

k = 2

那么，答案就是

1 + 2 + 3 + 4 + 5 + 1*2 + 1*3 + 1*4 + 1*5 + 2*3 + 2*4 + 2*5 + 3*4 + 3*5

非常感谢伪代码或一些关于如何更接近解决方案的指示。

Answer 1

令DP[i][j]:恰好大小为j的仅包含第[1~i]个元素的子集的乘积之和。

那么DP[i][j] = DP[i-1][j] + DP[i-1][j-1] * arr[i]

现在您可以在时间复杂度 O(NK) 上解决它。

== 编辑 ==

这是一个简单的代码。

int arr[1002]; /// The array where number is located
int DP[1002][1002];
int ans=0; /// final answer
DP[0][0] = 1;
for(int i=1; i<=n; i++){
    DP[i][0] = 1;
    for(int j=1; j<=i && j<=k; j++){
        DP[i][j] = DP[i-1][j] + DP[i-1][j-1] * arr[i];
    }
}
for(int i=1; i<=k; i++) ans+=DP[n][i];