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

小编典典

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

algorithm

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

问题是

查找其总数可被给定数整除的子数组的数目。

我的工作

我制定了一种算法，其复杂度为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;
 }

阅读 286

2020-07-28

共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。

我们可以将Bas 4*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映射到剩余值出现的频率（按预期构造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

2020-07-28