题目描述
给定一个长度为 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
算法1
(暴力枚举) $O(n)$
首先,这个题目O(n^2)是过不了的,想想优化
前缀和 (sum[r] - sum[l - 1]) % k = 0
sum[r] % k = sum [l - 1] % k
定义ans[i]代表1到i之前的数字前缀和取模的值
过程中会遇到相同的取值, 比如ans[a[1]] = 1,
ans[a[5]] = 1;
那在a[1] ~ a[5]之间也算一个k倍区间,所以 ans[sum[i]] ++;
代表a[5]之前的数字的解包括a[1]的解
但是会遇到 0 = 0的特殊情况,其实它也算是解之一,所以答案加上ans[0];
如果有不同想法,不妨在评论区下方分享你的想法吧,或许你的思路才是更好的捏😊😊😊
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL a[N], sum[N], ans[N];
void solve()
{
int n, k;
scanf("%d%d", &n, &k);
LL res = 0;
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
sum[i] = (sum[i - 1] + a[i]) % k;
res += ans[sum[i]];
ans[sum[i]] ++ ;
}
cout << res + ans[0]<< endl;
}
int main()
{
int t = 1;
while (t -- ) solve();
return 0;
}