[蓝桥杯 2017 省 B] k 倍区间
题目描述
给定一个长度为 N 的数列， 
, 
,⋯ 
，如果其中一段连续的子序列 
, 
,⋯ 
(i≤j) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K(1≤N,K≤ 
)。
以下 N 行每行包含一个整数 
(1≤ 
≤ 
)。
输出格式
输出一个整数，代表 K 倍区间的数目。
输入输出样例
输入 #1
5 2
1
2
3
4
5
输出 #1 6
说明/提示
时限 2 秒, 256M。蓝桥杯 2017 年第八届
对于这个题，先用了暴力枚举来解题，发现只能过两个样例，其他的都超时了，之后看了题解，他们用了前缀和思想，下面我就整理前缀和相关概念和解题方法。
前缀和
前缀和是什么？
通俗理解，前缀和就是任意一个元素前面所有元素的和（包括本身）；
例如：这有一个数组arr[3]={1,2,3}
如果设定一个数组为此数组的前缀和数组perfix[3]={1,3,6}
前缀和的好处
好处就是减少时间复杂度，例如上面的题，要求一段区间的和，用暴力枚举就会超时。使用前缀和，我们只需要用末尾的前缀和减去初位置的前缀和就可以得到该区间的和了；
我们来举个例子吧。定义一个arr[6]={1,2,3,4,5,6}，求这个数组的任意一个区间[i,j]的和
暴力枚举
我们肯定会从第一个元素开始，每次往后+1；然后从第二个元素开始，每次往后+1...;
假设要求[i,j]这个区间的和
for(int t=0;i<t;t++) int num1+=arr[t]; for(int m=j;m<=j;m++) int num2+=arr[m]; int num=num2-num1;
前缀和
定义一个 前缀和数组，从头开始求前缀和之后的前缀和就是前一个前缀和加上当前元素
prefix[0]=arr[0]; for(int n=0;n<arr.size;i++) prefix[n]=prefix[n-1]+arr[n]; int num=predix[j]-prefix[i-1];
prefix[j]-prefix[i-1]=arr[i]+arr[i+1]+...+arr[j];
因为这个题是一维的，我们就先介绍一维前缀和。
K倍区间解题思路
这个题不仅利用了前缀和还要转换思想，要求K的倍数，也就是是说根据前缀和里面的元素的运算得到的结果，只要没有余数就行，为防止数值溢出，我们可以只给前缀和里面存余数就行，余数如果为0，那么就是k的倍数。
因此这个前缀和数组中存的不是和，而是和的余数。具体操作如下：
prefix[0]=arr[0]; for(int n=0;n<arr.size;i++) prefix[n]=(prefix[n-1]+arr[n])/K;
第一步可以直接判断prefix数组里面的值是否0,等于0就是K 的倍数。
第二步就是中间子序列的值是否是K的倍数，令这个子序列的左下标为left,令右下标为right，那么子序列的和可以表示为prefix[right]-prefix[left-1],判断是不是K的倍数就是判断这个子序列的和除于K的余数是否为0。
（prefix[right]-prefix[left-1])%K==0
prefix[right]%K-prefix[left-1]%K==0
prefix[right]%K==prefix[left-1]%K
因此只要判断prefix[right]%K==prefix[left-1]%K就行，换个说法就是要找相同的有几个，假如有a个相同，这些相同的两两组合就可以构成一个子序列，也就是高中学的排列组合，我定义一个cnt数组，里面的数就代表i向同的有几个，然后两两组合，也就是
=
最后不要忘了前缀和里面单独余数为0的也是K的倍数，cnt[0]就是余数为0的个数。加上就行。
最后就是注意，记得数据类型定义为long long int
具体代码如下
#include<iostream> #include<vector> using namespace std; long long int n=1e6+10; int main() { long long int N,K,num=0,i; cin>>N>>K; vector <long long int>arr(n);//原数组 vector <int>prefix(n);//前缀和数组 vector <long long int>cnt(n); for(i=1;i<=N;i++) { cin>>arr[i];//数组输入 prefix[i]=(prefix[i-1]+arr[i])%K;//前缀和数组 cnt[prefix[i]]++;//统计里面相同的 } for(i=0;i<N;i++) { num+=cnt[i]*(cnt[i]-1)/2;//将相同的进行排列组合 } cout<<num+cnt[0];//余数为0的本来就是K的倍数 return 0; }
