本文共 1861 字,大约阅读时间需要 6 分钟。
给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗?
输入第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出输出一个整数,代表K倍区间的数目。
样例输入:
5 2 1 2 3 4 5程序应该输出:
6提示
资源约定:
峰值内存消耗(含虚拟机) < 256M CPU消耗 < 2000ms请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
注意:
main函数需要返回0; 只使用ANSI C/ANSI C++ 标准; 不要调用依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源文件中 #include 不能通过工程设置而省略常用头文件。提交程序时,注意选择所期望的语言类型和编译器类型。
比较容易想到的常规做法,是利用前缀和数组来保存整个数列的前缀和
然后再利用2层循环把所有的区间组合方案枚举出,对其中满足区间和为k的倍数的区间进行统计 最后输出结果即可 但是这里的数列最多达到了100000,在2层循环下,总的枚举次数就达到了O(1010)级,超时无疑 通常这种由数据范围带来的限制,往往需要通过数论的相关知识来进行优化 我们假设有一个序列为:5 2 4 7 3 1 6(且k=3),则其前缀和数组的增量对k取余的结果如下所示: a[ i ]表示该序列中的第 i 个数,S[ i ]表示该序列的前缀和增量对 k 取余的值(初始化S[0]=0) 不难看出,S[i]的取值在[0,k-1]之间,现在的问题是:这个值到底有什么用呢? 答案:S[i]出现的次数说明了截至当前i,前面的k倍区间的数量 比如在i=2时,当前S[i]=1,这是数字1的第一次出现,任何数字的第一次出现都不能说明前面的k倍区间数量。但是当之后再次出现了数字1时(比如上表中i=6处),则表明现在的这个位置与前面出现数字1的位置之间构成了一个k倍区间(不包括前一个位置的那个值)。比如区间[3,6](sum[3,6]=4+7+3+1=15,15%3=0)是一个k倍区间 继续看,在i=7时,S[i]=1又一次出现了,则表明在这个位置与其前面所有出现数字1的位置之间又能构成新的k倍区间(不包括前一个位置的那个值),比如区间[3,7](um[3,7]=4+7+3+1+6=21,21%3=0)是一个k倍区间;同时,也有区间[7,7](sum[7,7]=6,6%3=0)是一个k倍区间 …… 假设之后在某处i,又一次出现了数字1,那么该处又能与前面出现数字1的位置构成新的k倍区间。如果设在该处是数字1出现的第n次,那么此时能够构成的k倍区间就有n-1个,而总的k倍区间个数(包括前面所有的)则为:1+2+……+(n-1)此时有同学就会提问了:如果是数字0第一次出现(假设为位置i),那么此时的区间[1,i]不也是一个k倍区间么?
这个提问是正确的,比如对于上面的序列,按照之前的思路,我们的流程如下: 当i=4时数字0第1次出现,但是不能说明前面的k倍区间的数量;接着当i=5时数字0第2次出现,则表明此时区间[5,5](um[5,5]=3,3%3=0)是一个k倍区间 …… 就这样直到最后 而实际上,我们一开始就忽略了区间[1,4](sum[1,4]=5+2+4+7=18,18%3=0)也是一个k倍区间,这样的忽略导致之后每出现一次数字0,就忽略一次。比如当第2次出现数字0时,我们又忽略了区间[1,5](sum[1,5]=5+2+4+7+3=21,21%3=0)也是一个k倍区间…… 那么解决这个问题的办法也很简单,就是最后再单独加上一次所有的数字0出现的次数就行了 (思路参考于:https://blog.csdn.net/the_ZED/article/details/105046236)代码:
#include#include int a[100010]={ 0};int b[100010]={ 0};int main(){ int N,K; int t,i; scanf("%d%d",&N,&K); long long sum=0; for(i=0;i