长度为k的所有子数组元素乘积之和

Question

给定长度为n的数组。找到子数组元素乘积的总和。

解释：

数组A=[2,3,4]，长度为3。

长度为2的子数组=[2,3]、[3,4]、[2,4]

[2,3]中元素的积=6

[3,4]中元素的积=12

[2,4]中元素的积=8

长度为2的子数组之和=6+12+8=26

同理，长度为3的子数组之和=24

由于子数组元素乘积可能很大，因此计算时要对1000000007取模。如何高效地找到所有可能长度的子数组之和，即1、2、3......n，其中n是数组的长度。

- MetaD

---

n和k可以达到1000。 - MetaD

你所说的“高效”是否指除了显而易见的O（n ^ 3）之外的某些算法？ O（n ^ 2）可以接受吗？ - sve

如果像你的例子一样，“子数组”不是数组的子序列，而是包括非连续的部分，那么有n!/k!(n-k)!个子数组，并且你要对它们执行k次操作，似乎不太可能找到O(n*k)的解决方案。 - Pete Kirkham

@biziclop 是的，但如果您正在计算从1到N的k个组合的总和，那么您将涉及每个组合，因此仅对于求和而言，至少需要2^N次操作，假设在计算乘积时没有任何成本。到目前为止，大多数答案仅对(n-k)项进行求和，而不是像上面的示例一样对n!/k!(n-k)!项进行求和。 - Pete Kirkham

@MetaD 这是一个Project Euler的练习吗？如果这是一个在线问题，你能提供链接吗？谢谢。 - fjardon

Answer 1

有一个非常简单的方法：
构造项的乘积(1 + A[i] * x)：

P = (1 + A[0] * x) * (1 + A[1] * x) * (1 + A[2] * x)...*(1 + A[n-1] * x)

如果我们展开括号，那么我们会得到一个多项式。

P = 1 + B[1] * x + B[2] * x^2 + ... + B[n] * x^n

Kth系数，B[k]等于长度为K的集合的乘积之和 - 例如，B[n] = A[0]*A[1]*A[2]*..A[n-1], B[2] = A[0]*A[1] + A[0]*A[2] + ... + A[n-2]*A[n-1]等等。

因此，要找到所有可能集合的乘积之和，我们必须找到x = 1时多项式P的值，然后减去1以删除前导0次项。如果我们不想考虑单个元素集合，则需要减去B1= A[i]的总和。

示例：

(1+2)(1+3)(1+4) = 60
60 - 1 = 59
59 - (2 + 3 + 4) = 50 = 24 + 26 - as your example shows

- MBo

---

我没有正确阅读问题。我以为我们需要分别计算每个 k 的总和。这确实是正确的答案。 - Vincent van der Weele

如果我们只想要所有非空子集上的所有乘积之和，那么这应该是最有效的方法。如果我们想要部分和（即固定大小子集的和），那么我不知道如何从中提取它们。 - G. Bach

Answer 2

我们先创建一个递归关系。让f(n, k)表示长度为k的子数组乘积之和，来自长度为n的数组a。基本情况很简单：

f(0, k) = 0 for all k
f(n, 0) = 1 for all n

第二条规则可能有些违反直觉，但是1是乘法的零元素。

现在我们为f(n+1, k)找到一个递归关系。我们想要大小为k的所有子数组的乘积。这里有两种类型的子数组：包括a[n+1]和不包括a[n+1]的子数组。不包括a[n+1]的子数组的总和恰好是f(n, k)。包括a[n+1]的子数组恰好是添加了a[n+1]的长度为k-1的所有子数组，因此它们的总乘积是a[n+1]*f(n, k-1)。

这完成了我们的递归关系：

f(n, k) = 0                               if n = 0
        = 1                               if k = 0
        = f(n-1, k) + a[n] * f(n-1, k-1)  otherwise

你可以使用一个巧妙的技巧来限制动态规划所需的内存，因为函数 f 只依赖于前两个值：

int[] compute(int[] a) {
    int N = a.length;
    int[] f = int[N];
    f[0] = 1;

    for (int n = 1; n < N; n++) {
        for (int k = n; k >= 1; k--) {
            f[k] = (f[k] + a[n] * f[k-1]) % 1000000007;
        }
    }

    return f;
}

- Vincent van der Weele