查找数组的子数组,其数量除以给定数字

Question

我遇到了一个算法问题.请为我提出一些针对以下问题的有效算法.

问题是

查找数量的子数组,其总和可以被给定的数字整除.

我的工作

我做了一个算法,其复杂度为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;
 }

Answer 1

对于给定的数字X......

基本思路:(具有正确性的非正式证明)

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

(?i=1 to a-1input[i]) % X = (?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和A通过被划分X.

然后我们有:

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.

我们可以改写B为4*3 + 1和A作为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映射到剩余值出现的频率计数(按预期构造O(n)).

将0值增加1 - 这对应于数组的开头.

将计数初始化为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