题目描述
给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,
我们就称这个区间 [i,j] 是 K倍区间。你能求出数列中总共有多少个 K倍区间吗?
-
k倍区间?是不是小脑袋瓜氤氲了一下?
-
区间查找?O(N)枚举起始点?O(N)扫描?————O(N^2)算法。只要N<1e4,轻轻松松暴力到手(嘿嘿)
-
看一下数据范围————(1≤N,K≤100000,1≤Ai≤100000),这怎么可能? 给我10秒我都过不去啊(QAQ)
年轻人要淡定,可以优化的啦~ 再来读一遍题目(答案在题干中嘛)
给定一个长度为 N 的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数,
我们就称这个区间 [i,j] 是 K倍区间。这个“连续”“和”用的妙啊 balabala(以下省略一万字)
是不是想到了前缀和?
有人就要说了,前缀和有什么用?我时间复杂度还是(N^2),优化了个寂寞啊
莫慌莫慌,继续分析
既然是k的倍数,那我取个模是不是可以避免开 long long 优化空间。(啪,大嘴巴子)
别打人,年轻人要耐心,其实答案已经出来了
k倍等价于模k等于0,所以只要两个前缀和对k的模相同那不就ok啦
为了避免再次O(N)比对前缀和的模,用一个桶把余数装起来好了,分析完毕,搞它
C++ 代码
#include<bits/stdc++.h>
#define N 1000000
using namespace std;
int n, k, sum[N], a[N];
long long ans, mod[N]; //10年OI,不开long long一场空 ,90分大礼包领回家
int main()
{
cin>> n >> k;
for(int i = 1 ; i <= n; i++)
{
cin>> a[i];
sum[i] = ( sum[i-1] + a[i] ) % k;
ans += mod[sum[i]];
mod[sum[i]]++;
}
printf("%lld",ans+mod[0]);//本来就是k的倍数你不加是不是..(懂的都懂)
return 0;
}