AcWing 1230. K倍区间
原题链接
中等
作者:
醉酒夢紅顏
,
2023-02-14 17:29:17
,
所有人可见
,
阅读 121
只遍历一次前缀和数组,就可以找到所有子序列,是因为在找到一个区间满足条件后,将此区间记录下来,将记录区级个数的变量加一,当有端点继续移动,找到下一个满足条件的区间时,之前找到的那个区间此时就成了当前区间的一个字区间
要将记录区间个数的数组开始时cnt[0]++,是因为s[0]==0,所以s[0]%k也为0,也是一个满足条件的区间
数据范围为 1≤N,K≤100000 1≤Ai≤100000 当有十万个数,每个数的大小为十万时,当这十万个数相加时,结果为十万*十万,大于INT_MAX,所以前缀和数组要开long long; 当有十万个数时,符合条件的区间个数为n+(n-1)+···+1=n(n+1)/2,超出int 范围,所以结果数也用long long 来存
代码:
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e6+10;
int cnt[N];
long long a[N];
int res=0;
int n,k;
int main()
{
cin>>n>>k;
for (int i=1;i<=n;i++)
{
cin>>a[i];
a[i]+=a[i-1];
}
cnt[0]++;
for (int i=1;i<=n;i++)
{
res+=cnt[a[i]%k];
cnt[a[i]%k]++;
}
cout<<res<<endl;
return 0;
}