求和除以给定数的数组的子数组数 [英] Find numbers of subarray of an array whose sum is divided by given number
问题描述
我被一个算法问题困住了.请为我提出一些针对以下问题的有效算法.
I got stuck in one algorithm question. Please suggest me some efficient algorithm for the below problem.
问题是
求和能被给定数整除的子数组的个数.
Find numbers of subarrays whose sum is divisible by given number.
我的工作
我做了一个算法，它的复杂度是 O(N^2)，这里，N = 数组的大小.
I made one algorithm, whose complexity is O(N^2), here, N = size of an array.
我的代码
#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;
}
推荐答案
对于给定的数字 X...
For a given number X...
基本思想:(带有非正式的正确性证明)
The basic idea: (with informal proof of correctness)
如果[a, b]范围内的数字之和能被X整除，则:
If the sum of the numbers in the range [a, b] is divisible by X, then:
(∑i=1 to a-1input[i]) % X = (∑i=1 to binput[i]) %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整除.详细说明:
Then, if those sums on the right both have the same remainder when divided by X, the remainders will cancel out and sum of the elements between the two will be divisible by X. An elaboration:
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，＜X.这里，根据定义，Q 和 S 将分别是 B 和 A 除以 的余数>X.
Now we can convert B to the form PX + Q and A to the form RX + S, for some integers P, Q, R and S, with 0 <= Q, S < X. Here, by definition, Q and S would be the respective remainders of B and A being divided by 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
Clearly (P-R)X is divisible by X (the result is simply (P-R)). Now we just need Q - S to be divisible by X, but, since 0 <= Q, S < X, they'll need to be equal.
示例:
设 B = 13, A = 7, X = 3.
这里 B % X = 1 和 A % X = 1.
我们可以将B重写为4*3 + 1，将A重写为2*3 + 1.
We can rewrite B as 4*3 + 1 and A as 2*3 + 1.
那么C = 4*3 + 1 - 2*3 - 1 = 2*3，可以被3整除.
高级方法:
构造一个 key -> 的哈希映射值，其中每个值表示从数组的开头开始到某个给定位置可以有多少种方式，这些方式加起来等于 sum mod X = key(请参阅Mod3" 线和下面示例中的地图值).
Construct a hash-map of key -> value, where each value represents how many ways you can start from the beginning of the array and end up at some given position which adds up to sum mod X = key (see the "Mod 3" line and the map values in the example below).
现在，根据上面的逻辑，我们知道如果两个子数组分别从位置a和b开始到结束，都具有相同的sum mod X，子数组 [a, b] 将被 X 整除.
Now, based on the logic above, we know that if two subarrays starting from the beginning and ending at positions a and b respectively, both having the same sum mod X, subarray [a, b] will be divisible by X.
所以哈希图中的每个值代表一组可能的起点和终点的大小，这将给我们一个可以被 X 整除的子数组(任何点都可以是起点或终点).
So each value in the hash-map represents the size of a set of possible starting and ending points which will give us a subarray divisible by X (any point can be either a starting or ending point).
选择这些起点和终点的可能方式的数量很简单value select 2 = value!/(2*(value-2)!)(如果值为 1，则为 0).
The number of possible ways to choose these starting and ending points is simply
value choose 2 = value!/(2*(value-2)!) (or 0 if value is 1).
所以我们计算散列映射中的每个值并将它们全部加起来得到可被X整除的子数组的数量.
So we calculate that for each value in the hash-map and add them all up to get the number of subarrays divisible by X.
算法:
构造一个哈希映射，它将存储迄今为止所有数字的累积总和 mod X 映射到该余数值出现的频率的计数(以预期的 O(n)).
Construct a hash-map which will store the cumulative sum of all the numbers thus far mod X mapped to the count of how often that remainder value appears (constructed in expected O(n)).
将 0 的值加一 - 这对应于数组的开头.
Increase 0's value by one - this corresponds to the start of the array.
将计数初始化为 0.
对于哈希图中的每个值，将 value!/(2*(value-2)!) 添加到计数中.
For each value in the hash-map, add value!/(2*(value-2)!) to the count.
计数是所需的值.
运行时间:
预期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
这篇关于求和除以给定数的数组的子数组数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
