AcWing 1230. K倍区间
原题链接
中等
作者:
Bear_King
,
2021-01-11 17:45:37
,
所有人可见
,
阅读 389
K倍区间
实质:对每一段连续子序列操作,暴力直接O(n^3)
优化:把最暴力的O(n^3)优化成O(n)阶的版本(如下代码):
优化过程:暴力三层循环O(n^3) -> 把第三层循环用前缀和优化O(n^2) -> 把内层循环从性质规律的角度,进行模拟推导优化O(n)
#include<iostream>
using namespace std;
const int N = 100010;
typedef long long LL; //防止炸int
LL s[N],cnt[N]; //s前缀和数组,cnt 除K得余数值的模拟数组
int n,k;
int main()
{
scanf("%d%d",&n,&k);
//输入操作+前缀和预处理
for(int i = 1;i <= n;i ++)
{
scanf("%d",&s[i]);
s[i] += s[i-1];
}
//res答案初始0,且0也是余数+1
LL res = 0;
cnt[0] = 1;
for(int i = 1;i <= n;i ++)
{
res += cnt[s[i] % k];//从0~r-1直接对于(s[r]-s[l])%k==0做处理成:有多少个s[l]与s[r]对k的余数相同
/*
所以就遇到一个s[r]就把它对k取余在cnt余数数组里面进行模拟余数的个数,
第一次累加0,第二次即为s[l]与s[r]相同,就直接累加1,说明成立一个,以此类推下去,
找出所有符合余数的s[l]%k == s[r]%k 的情况,最后输出res即为最终答案
*/
cnt[s[i] % k] ++;
}
printf("%lld",res);
}