我被一道算法题卡住了。请建议我一些有效的算法来解决以下问题。
问题是
找出其和可被给定数整除的子数组的数目。
我的作品
我做了一个算法，它的复杂度是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;
}
对于给定的数字 X ...
基本思想:(带有非正式的正确性证明)
如果[a, b]范围内的数字之和可以被 X 整除，然后:
(∑<sub>i=1 to a-1</sub>input[i]) % X = (∑<sub>i=1 to b</sub>input[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 的 HashMap ，其中每个值表示您可以从数组的开头开始并在某个给定位置结束的方式，这些方式加起来为 sum mod X = key (参见下面示例中的“Mod 3”行和映射值)。
现在，根据上面的逻辑，我们知道如果两个子数组从头开始到位置a结束。和 b分别具有相同的 sum mod X , 子数组 [a, b]将被 X 整除.
因此 HashMap 中的每个值都代表一组可能的起点和终点的大小，这将为我们提供一个可被 X 整除的子数组。 (任何一点都可以是起点或终点)。
选择这些起点和终点的可能方式的数量很简单
value choose 2 = value!/(2*(value-2)!) (如果值为 1，则为 0)。
因此我们计算 HashMap 中的每个值并将它们全部相加以获得可被 X 整除的子数组的数量.
算法:
构造一个 HashMap ，它将存储迄今为止所有数字的累计和mod X映射到剩余值出现频率的计数(在预期 O(n) 中构建)。
增加0的值加一 - 这对应于数组的开头。
将计数初始化为 0。
对于 HashMap 中的每个值，添加 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