题目描述
给定一个长度为 $N$ 的数列,$A_1,A_2,\dots A_N$,如果其中一段连续的子序列 $A_i,A_{i+1},\dots A_j$ 之和是 $K$ 的倍数,我们就称这个区间 $[i,j]$ 是 $K$ 倍区间。
你能求出数列中总共有多少个 $K$ 倍区间吗?
输入格式
第一行包含两个整数 $N$ 和 $K$。
以下 $N$ 行每行包含一个整数 $A_i$。
输出格式
输出一个整数,代表 $K$ 倍区间的数目。
数据范围
$1≤N,K≤100000,$
$1≤A_i≤100000$
样例
输入样例
5 2
1
2
3
4
5
输出样例
6
思路
本来想的是写个嵌套循环,没想到学识短浅,TLE了,于是改用同余定理。
前缀和
一维数组$a[n]$前缀和$b[n]$:
$$
b[i] = b[i-1] + a[i]
$$
则对于区间$[i,j]$,$A_i,A_{i+1},\dots A_j$之和
$$
sum[i,j] = b[j] - b[i-1]
$$
同余定理
给定一个正整数$m$,如果两个整数$a$和$b$满足$a-b$能够被$m$整除,即$(a-b)/m$得到一个整数,那么就称整数$a$与$b$对模$m$同余,记作$a≡b(mod\; m)$。对模$m$同余是整数的一个等价关系。
在本题中,我们是两个前缀和同余,那么这个区间可以被$K$整除。
解法1
C++ 代码
#include <bits/stdc++.h>
int a[100005];
long long b[100005];
long long ans[100005];
int main(){
int N, K;
long long cnt = 0;
scanf("%d %d", &N, &K);
for(int i = 1; i <= N; i ++){ //从n=1开始,不错
scanf("%d", &a[i]);
b[i] = b[i-1] + a[i];
}
ans[0] = 1; //b[0] = 0
//区间的定义:[a, b] 其中a<=x<=b,a和b可以相等
//区间和表示:sum[i,j] = b[j] - b[i-1]
for(int i = 1; i <= N; i ++){
ans[b[i]%K] ++;
}
for(int i = 0; i < K; i ++){
cnt += ans[i]*(ans[i]-1)/2;
}
printf("%lld\n", cnt); //长整型是lld
return 0;
}
注意点
- 区间的定义:[a, b] 其中a<=x<=b,a和b可以相等
- 使用printf时,长整型是lld
- ans数组计算完毕之后,在每个下标中对其进行排列组合,每个都为$C_i^2$,即$i*(i-1)/2$
解法2
我是搬运工
参考文献
https://www.acwing.com/solution/content/6909/
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int sum[N],a[N],res[N];
int n,k;
ll ans=0;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=(sum[i-1]+a[i])%k;//前缀和取模
ans+=res[sum[i]];//更新答案
//对于这个有问题的同学可以参见下面的评论 佐以理解
res[sum[i]]++;//两个相等的前缀和就能组成一个k倍区间
}
cout<<ans+res[0]<<endl;
return 0;
}
注意点
其中,对于 ans+=res[sum[i]];
的理解:
首先明确 res[sum[i]]
表示的是sum[i]
出现过的次数。
举个例子,假设 sum[i] = 3
,在后边的循环中,又出现了一个 sum[i] = 3
,那么此时,这个“3”可以和前边出现过的所有的“3”分别构成一个$K$倍区间,前边的“3”一共出现过res[sum[i]]
次,所以 此时又新增了res[sum[i]]
个$K$倍区间。