AcWing 1230. K倍区间
思路
求区间的和为k的倍数的区间的个数。首先前缀和数组处理出来。
数据范围1e5,要想想O(n)或者O(logn)做法
将前缀和数组\(s[n]\)处理出来。
注意:
以i为右端点,长度为1的区间和为\(a[i]\),即\(s[i]-s[i-1]\)
以i为右端点,长度为2的区间和为\(a[i-1]+a[i]\),即\(s[i]-s[i-2]\)
...
以i为右端点,长度为i的区间和为\(a[1]+a[2]+...+a[i]\),即\(s[i]-s[0]\)即\(s[i]\)
我们枚举以i为右端点的区间,我们观察以i为右端的区间长度为1,2,3,...,i-1,i的区间和,即前缀和数组表达出来是\(s[i]-s[i-1]、s[i]-s[i-2]、s[i]-s[i-3],...,s[i]-s[1],s[i]-s[0]\)这些个值。
某个区间和为k的倍数:
比如\([i-1,i]\)这个区间\(s[i] - s[i-1] \equiv 0 \, (mod \, k)\),s[i]-s[i-1]是k的倍数,所以\(s[i]-s[i-1]\)与\(0\)模\(k\)同余。
所以有\(s[i] \equiv s[i-1] \, (mod \, k)\)
所以找模k余数相同的数的个数即可,使用哈希表来存储。
每个s[i]记录到哈希表\(cnt[s[i] \, mod \,k]\)
关于边界:s[0]也要去统计进哈希表 即需要先cnt[0] ++(以i为右端点,长度为i的区间)。
代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n,k;
LL s[N],cnt[N];
int main()
{
cin >> n >> k;
for(int i = 1;i <= n;i ++)
{
cin >> s[i];
s[i] += s[i-1];
}
LL res = 0;
cnt[0] ++;
for(int i = 1;i <= n;i ++)
{
res += cnt[s[i] % k];
cnt[s[i] % k] ++;
}
cout << res;
return 0;
}
标签:cnt,1230,哈希,int,端点,区间,长度,AcWing
From: https://www.cnblogs.com/rdisheng/p/17138482.html