所有长度为k的子阵列的元素的乘积之和

Question

给出了长度为n的数组.找到子数组元素的乘积之和.

说明

数组A = 长度为3的[2,3,4].

长度为2 = [2,3],[3,4],[2,4]的子阵列

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

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

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

长度为2 = 6 + 12 + 8 = 26的子阵列的总和

类似地,对于长度3,Sum = 24

因为,对于更高长度的子阵列,产品可以更大,以模1000000007计算.

找到所有可能长度的子阵列的这些总和的有效方法是什么,即1,2,3,......,n,其中n是阵列的长度.

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

Answer 2

我们首先创建一个递归关系。令f(n, k)为length的子数组与length k的数组a的所有乘积之和n。基本情况很简单：

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

第二个规则似乎有点违反直觉，但是1是乘法的零元素。

现在我们找到的递归关系f(n+1, k)。我们需要size个子数组的乘积k。这里有两种类型的子数组：包含的子数组a[n+1]和不包含的子数组a[n+1]。不包括在内的总和a[n+1]就是f(n, k)。所包含a[n+1]的恰好是所有长度加k-1在一起的子数组a[n+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;
}