前缀和与差分

1. K倍区间

来源：第八届蓝桥杯省赛C++B组,第八届蓝桥杯省赛JAVAB组
原题链接

题目描述

给定一个长度为 \(N\) 的数列，\(A_1,A_2,…A_N\)，如果其中一段连续的子序列 \(A_i,A_{i+1},…A_j\) 之和是 \(K\) 的倍数，我们就称这个区间 \([i,j]\) 是 \(K\) 倍区间。

你能求出数列中总共有多少个 \(K\) 倍区间吗？

输入格式

第一行包含两个整数 \(N\) 和 \(K\)。

以下 \(N\) 行每行包含一个整数 \(A_i\)。

输出格式

输出一个整数，代表 \(K\) 倍区间的数目。

数据范围

\(1≤N,K≤100000\),
\(1≤A_i≤100000\)

输入样例

5 2
1
2
3
4
5

输出样例

6

算法：（前缀和 + 哈希表）\(O(n)\)

算法内容

• 暴力做法：
  我们先预处理前缀和，用\(i\)和\(j\)暴力枚举所有区间，每一次判断区间[j, i]是否满足\((s[i] - s[j - 1])\) % \(k\) \(=\) \(0\)，若满足答案加\(1\)，但是会循环\(\frac{n^2}{2}\)次，时间复杂度为\(n^2\)，会TLE

• 我们如何优化？
  我们可以只用\(i\)枚举区间的右端点，对于所有以\(i\)为右端点的区间我们要找的是\(i\)前面有多少数满足：
  \(s[i] - s[i - 1]\) % \(k\) \(=\) \(0\) \(\iff\) \(s[i]\) % \(k\) \(=\) \(s[i - 1]\) % \(k\)
  \(s[i] - s[i - 2]\) % \(k\) \(=\) \(0\) \(\iff\) \(s[i]\) % \(k\) \(=\) \(s[i - 2]\) % \(k\)
  \(s[i] - s[i - 3]\) % \(k\) \(=\) \(0\) \(\iff\) \(s[i]\) % \(k\) \(=\) \(s[i - 3]\) % \(k\)
  ···
  \(s[i] - s[0]\) % \(k\) \(=\) \(0\) \(\iff\) \(s[i]\) % \(k\) \(=\) \(s[0]\) % \(k\)
  问题转化为s[i]前面有多少个数满足它除以\(k\)的余数是\(s[i]\) % \(k\)，所以我们可以用哈希表记录s数组中\(i\)前面的所有的数除以\(k\)的每一种余数的出现次数，每一次循环查表\(s[i]\) % \(k\)的次数，并累加，然后更新哈希表。

• 注意：
  1.答案最多为\(\frac{n^2}{2}\)个，可能爆\(int\)；前缀和数组最大的值可能为\(N*K\)个，也可能爆\(int\)
  2.最开始循环时，\(i = 1\)，一定记得将\(s[0]\)的信息插到哈希表中，因为\(s[0] = 0\)，所以\(s[0]\) % \(k\) \(=\) \(0\)，出现\(1\)次
  3.每一次循环结束记得把\(s[i]\)的信息加到哈希表中

C++代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL s[N], cnt[N];

int main()
{
    scanf("%d%d", &n, &k);
    
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    LL res = 0;
    cnt[0] = 1; //一定要初始化是前面的s0的信息，因为s0 = 0，所以s0 % k = 0出现一次
    for (int i = 1; i <= n; i ++ )
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++ ;
    }

    printf("%lld\n", res);

    return 0;
}