0

给定一个数组，找出存在多少这样的子序列（不需要是连续的），其中该子数组中的元素之和可以被 K 整除。

我知道一种复杂度为 2^n 的方法，如下所示。这就像找到 i=[0,n] 的所有 nCi 并验证总和是否可被 K 整除。请提供类似线性/二次或 n^3 的伪代码。

static int numways = 0;
void findNumOfSubArrays(int  [] arr,int index, int sum, int K) {
        if(index==arr.length) {
                if(sum%k==0) numways++;
        }
        else {
                findNumOfSubArrays(arr, index+1, sum, K);
                findNumOfSubArrays(arr, index+1, sum+arr[index], K);
        }
}
4

3 回答 3

2

输入 - 长度为 n 和自然数 k 的数组 A。

算法：

  • 构造数组 B：对于每个 1 <= i <= n：B[i] = (A[i] modulo K)。

现在我们可以使用动态规划：

我们定义 D[i,j] = - B[i..n] 的最大子数组数，它的元素之和模 k 等于 j。

1 <= 我 <= n。0 <= j <= k-1。

D[n,0] = if (b[n] == 0), 2. 否则为 1。

如果 j > 0 ：

D[n,j] = if (B[n] modulo k) == j, 大于 1。否则为 0。

对于 i < n 和 0 <= j <= k-1：

D[i,j] = max{D[i+1,j], 1 + D[i+1, D[i+1,(jB[i]+k) 模 k)]}。

  • 构造 D。

  • 返回 D[1,0]。

总运行时间：O(n*k)

于 2012-08-02T06:59:24.813 回答
0

使用辅助数组A

1) 在接受输入时，将当前总计存储在相应的索引中（这在 中执行O(n)）：

int sum = 0;
for (int i = 0; i < n; i++)
{
    cin >> arr[i];
    sum += arr[i];
    A[i] = sum;
}

2）现在，

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        check that (A[j] - A[i] + arr[i]) is divisible by k

给你：O(n^2)...

于 2012-08-02T06:58:35.377 回答
0

实际上，如果 K 的范围和数组中的数字范围未知，我认为这个问题不可能在 O(n^3) 甚至多项式时间内解决。这是我的想法：

考虑以下情况： arr 中的 N 个数字类似于

[1,2,4,8,16,32,...,2^(N-1)]

,

这样，arr 的 2^N 个“子数组”（不需要连续）的总和正好是 [0,2^N) 中的所有整数

并且问其中有多少能被K整除，相当于问[0, 2^N)中有多少整数能被K整除。

我知道在上述情况下，答案可以像 (2^N-1)/K （或其他东西）一样直接计算出来。但是，如果我们只是随机更改 arr 中的几个（可能是 3 个？4 个？）数字，以在完美连续整数范围 [0,2^N）中“挖一些随机洞”，这看起来不可能无需遍历 [0,2^N) 中的几乎所有数字即可计算答案。

好吧，只是一些愚蠢的想法......可能是完全错误的。

于 2012-08-02T08:08:06.707 回答