5

我陷入了一个算法问题。请为以下问题建议一些有效的算法。

问题是

查找总和可被给定数字整除的子数组的数量。

我的工作

我做了一个算法，它的复杂度是 O(N^2)，这里，N = 数组的大小。

我的代码

#include<stdio.h>

using namespace std;

 main() {
    int N;
    int P;
    int T;
    int val;
    long long int count = 0;
    long long int answer = 0;
    scanf("%d", &T);
    //T = 20;

    for(int k = 1; k <= T; k++) {
        scanf("%d", &N);
        scanf("%d", &P);
        count = 0;
        answer = 0;
        for(int i = 0; i < N; i++) {
            scanf("%d", &val);
            count += val;
            workingArray[i] = count;
        }

        for(int length = 1; length <= N; length++) {
            for(int start = 0; start <= (N-length); start++) {
                if( start == 0 ) {
                    if(workingArray[start+length-1]%P == 0) answer++;
                }
                else if( (workingArray[start+length-1] - workingArray[start-1])%P == 0) answer++;
            }
        }

        printf("Case #%d\n%lld\n", k, answer);
    }
    return 0;
 }
4

2 回答 2

27

对于给定的数字X...

基本思想：（带有正确性的非正式证明）

如果范围内的数字之和可以[a, b]被 整除X，则：

(∑<sub>i=1 to a-1input[i]) % X = (∑<sub>i=1 to binput[i]) % X

用较少的数学术语：

the sum from the first element to b = the sum from the first element to a
                                    + the sum of the elements between the two

所以：

the sum of the elements between the two = the sum from the first element to b
                                        - the sum from the first element to a

然后，如果右边的这些和除以 时具有相同的余数X，则余数将抵消并且两者之间的元素之和将被 整除X。详细说明：

C = the sum of the elements between the two
B = the sum from the first element to b
A = the sum from the first element to a

现在我们可以转换B为形式PX + Q和A形式RX + S，对于一些整数P, Q,R和S, 0 <= Q, S < X。这里，根据定义，Q和S​​分别是 的余数B并被.AX

然后我们有：

C = (PX + Q) - (RX + S)
C = PX + Q - RX - S
C = PX - RX + Q - S
C = (P-R)X + Q - S

显然(P-R)X可以被X（结果只是(P-R)）整除。现在我们只需要Q - S被 整除X，但是，因为0 <= Q, S < X，它们需要相等。

例子：

让B = 13, A = 7, X = 3.

这里B % X = 1和A % X = 1。

我们可以重写Bas4*3 + 1和Aas 2*3 + 1。

那么C = 4*3 + 1 - 2*3 - 1 = 2*3， 可以被 整除3。

高级方法：

构造一个 的哈希映射key -> value，其中每个值表示您可以从数组的开头开始并在某个给定位置结束的方式，这些方式加起来是sum mod X = key（参见“Mod 3”行和下面示例中的映射值）。

现在，根据上面的逻辑，我们知道如果两个子数组从头开始和分别在位置a和结束b，都具有相同的sum mod X，子数组[a, b]将被 整除X。

因此，哈希图中的每个值都表示一组可能的起点和终点的大小，这将为我们提供一个可被整除的子数组X（任何点都可以是起点或终点）。

选择这些起点和终点的可能方法的数量很简单
value choose 2 = value!/(2*(value-2)!)（如果值为 1，则为 0）。

因此，我们计算哈希图中的每个值并将它们全部加起来以获得可被 整除的子数组的数量X。

算法：

构造一个哈希映射，它将存储迄今为止mod X映射到该剩余值出现频率的计数的所有数字的累积总和（在 expected 中构建O(n)）。

将0的值加一 - 这对应于数组的开头。

将计数初始化为 0。

对于散列图中的每个值，添加value!/(2*(value-2)!)到计数中。

计数是所需的值。

运行时间：

预期O(n)。

例子：

Input:    0  5  3  8  2  1
X = 3

Sum:   0  0  5  8 16 18 19
Mod 3: 0  0  2  2  1  0  1

Map:
  0 -> 3
  1 -> 2
  2 -> 2

Count = 3! / 2*(3-2)! = 3  +
        2! / 2*(2-2)! = 1  +
        2! / 2*(2-2)! = 1
      = 5

子数组将是：

0  5  3  8  2  1
-                     0                 =  0 % 3 = 0
-------------         0 + 5 + 3 + 8 + 2 = 18 % 3 = 0
   ----------         5 + 3 + 8 + 2     = 18 % 3 = 0
      -               3                 =  3 % 3 = 0
            ----      2 + 1             =  3 % 3 = 0
于 2013-10-23T12:25:13.083 回答
1

我可能有一个更简单的解决方案。在 O(n) 时间和 O(n+k) 空间中。其中 n 是数组的大小 & k 是我们检查可分性的数字。

将数组视为 A[n]，数字为 K

  1. 创建另一个数组 SUM_TILL_NOW[n]。
  2. 对于每个 A[i] 填充 SUM_TILL_NOW [i]= SUM_TILL_NOW[i-1]+A[i] %K; (SUM_TILL_NOW[0]= A[0])
  3. 在这个新数组中找到两个相等的数字。

为此，创建一个大小为 K 的新数组 CHECK[]。

遍历 SUM_TILL_NOW 数组并检查是否设置了 CHECK[SUM_TILL_NOW[i]]。

如果不设置为 i。

else CHECK[SUM_TILL_NOW[i]], i 是总和可被 K 整除的子集。

下面是一个相同的c++函数。

#include <iostream>
#include <string.h>

using namespace std;

void printrange(int* A, int N, int K)
{
    int STN[N], C[K];
    memset(C, -1, K*sizeof(int));
    int i;
    int sum=A[0];
    STN[0]= (A[0]%K);
    for (i= 1; i< N; i++)
    {
        sum+= A[i];
        STN[i]= sum%K;
    }
    for(i=0; i< N; i++)
    {
        if(C[STN[i]] == -1)
            C[STN[i]] =i;
        else
        {
            cout<< C[STN[i]]+1 <<" "<< i;
            break;
        }
    }
}

int main()
{
    int A[]= {6, 9, 2, 1, 8, 6, 2, 5};
    printrange(A, sizeof(A)/sizeof(A[0]), 7);
    return 0;
}
于 2014-03-04T19:33:52.223 回答