题目描述
给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,我们就称这个区间 [i,j] 是 K倍区间。你能求出数列中总共有多少个 K倍区间吗?
输入格式
第一行包含两个整数 N和 K
以下 N行每行包含一个整数 Ai。
输出格式
输出一个整数,代表K倍区间的数目。
数据范围
1≤N,K≤100000,
1≤Ai≤100000
样例
输入样例:
5 2
1
2
3
4
5
输出样例:
6
这个题暴力肯定超时。暴力代码很简单,直接套模板,但是只能过部分样例。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int cnt[0];//记录余数为i的个数
long long s[100005];//前缀和
int n,k;
long long res;
int main(int argc, char** argv) {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
s[i]+=s[i-1];//求前缀和
}
for(int r=1;r<=n;r++){
for(int l=1;l<=r;l++){
if((s[r]-s[l-1])%k==0){
res++;
}
}
}
printf("%lld",res);
return 0;
}
扩模运算法则
运算规则
模运算与基本四则运算有些相似,但是除法例外。其规则如下:
(a + b) % p = (a % p + b % p) % p (1)
(a - b) % p = (a % p - b % p ) % p (2)
(a * b) % p = (a % p * b % p) % p (3)
a ^ b % p = ((a % p)^b) % p (4)
结合律:
((a+b) % p + c) % p = (a + (b+c) % p) % p (5)
((ab) % p * c)% p = (a * (bc) % p) % p (6)
交换律:
(a + b) % p = (b+a) % p (7)
(a * b) % p = (b * a) % p (8)
分配律:
(a+b) % p = ( a % p + b % p ) % p (9)
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p (10)
运算规则
模运算与基本四则运算有些相似,但是除法例外。其规则如下:
(a + b) % p = (a % p + b % p) % p (1)
(a - b) % p = (a % p - b % p ) % p (2)
(a * b) % p = (a % p * b % p) % p (3)
a ^ b % p = ((a % p)^b) % p (4)
结合律:
((a+b) % p + c) % p = (a + (b+c) % p) % p (5)
((ab) % p * c)% p = (a * (bc) % p) % p (6)
交换律:
(a + b) % p = (b+a) % p (7)
(a * b) % p = (b * a) % p (8)
分配律:
(a+b) % p = ( a % p + b % p ) % p (9)
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p (10)
下面就想优化的方法吧
一
一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,其实就是第l个到第r个数的和是k的倍数,第l个到第r个数的和可以用s[r]-s[l-1];(s[r]-s[l-1])%k==0的情况下就说明符合情况,K 倍区间的数目就加1;(s[r]-s[l-1])%k==0可以看成是s[r]%k==s[l-1]%k,对前缀和取模之后,两个相等的前缀和就能组成一个k倍区间。
我们可以用一个数组cnt,规定cnt[i]表示当前位置之前,前缀和取模后等于i的个数,以后每出现一次前缀和(取模后)和它相等,那么k倍区间就加上cnt[s[i]],然后cnt[s[i]]++。这样似乎不容易理解,我们用样例举个例子。
对于数列 1 2 3 4 5,k = 2
对前1个数的和模k后为1,在此之前有0个前缀和取模后为1,总个数+0
对前2个数的和模k后为1,在此之前有1个前缀和取模后为1,总个数+1
对前3个数的和模k后为0,在此之前有0个前缀和取模后为0, 总个数+0
对前4个数的和模k后为0,在此之前有1个前缀和取模后为0,总个数+1
对前5个数的和模k后为1,在此之前有2个前缀和取模后为1,总个数+2
其实我们忽略了一个东西,当某个位置i的前缀和它本身就是k的倍数,那么原数组1到这个位置的所有数的和(s[i]-s[0]是一个k倍区间,所以最后要加上cnt[0] (余数为0的个数)
当某个位置i的前缀和它本身就是k的倍数,那么原数组1到这个位置的所有数的和(s[i]-s[0]是一个k倍区间,这个问题,我们其实可以把cnt[0]赋值为1,最后就不用加cnt[0]了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int cnt[100005];//记录余数为i的个数
long long s[100005];//原数组,前缀和数组共用一个数组,节省内存
int n,k;
long long res; //long long可能会爆int
int main(int argc, char** argv) {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
s[i]=(s[i]+s[i-1])%k;//优化,要不断取模,事实上影响能否整除这一性质的只有余数,所以保存取模的结果即可
res+=cnt[s[i]%k];
//用一个数组cnt,规定cnt[i]表示当前位置之前,前缀和取模后等于i的个数,
//以后每出现一次前缀和(取模后)和它相等,那么k倍区间就加上cnt[s[i]],然后cnt[s[i]]++。
cnt[s[i]%k]++;
}
printf("%lld",cnt[0]+res);
return 0;
}
二
余数最大只能是k-1,最小是0,统计出余数为i(0~k-1)的个数分别是多少,然后从余数为i(0~k-1)的里面任意拿出两个就是一种k倍区间,例如余数为1的个数为n,则就有n*(n-1)/2种情况
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int cnt[100005];//记录余数为i的个数
int s[100005];//前缀和
int n,k;
long long res;
int main(int argc, char** argv) {
scanf("%d%d",&n,&k);
cnt[0]=1;
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
s[i]=(s[i-1]+s[i])%k;//前缀和优化
cnt[s[i]]++;//记录前缀和余数为i的个数
}
for(int i=0;i<k;i++){
res+=(long long)cnt[i]*(cnt[i]-1)/2;//cnt[i]*(cnt[i]-1)会爆int所以是long long
}
printf("%lld",res);
return 0;
}