AcWing 1230. 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≤Ai≤100000$

输入样例：

5 2
1
2
3
4
5

输出样例：

6

前缀和

首先预处理出前缀和数组，再考虑暴力做法。枚举每一段区间，计算一次区间和，判断是否为 $k$ 的倍数。
这样，复杂度为 $O(N^2)$, 数据范围 $1≤N,K≤100000$ ，复杂度高达 $10^{10}$. 必然TLE。

那么复杂度至少要求低于 $O(NlogN)$。

统计以 $i$ 结尾的子数组的和是否为 $k$ 的倍数，共有长度从 $1$~$i$ 共 $i$ 种情况：

长度	子数组的和	对k取余数
$1$	$s[i - 1] - s[i]$	$(s[i] - s[i - 1]) \bmod k$
$2$	$s[i - 2] - s[i]$	$(s[i] - s[i - 2]) \bmod k$
$3$	$s[i - 3] - s[i]$	$(s[i] - s[i - 3]) \bmod k$
…
$i-1$	$s[1] - s[i]$	$(s[i] - s[1]) \bmod k$
$i$	$s[0] - s[i]$	$(s[i] - s[0]) \bmod k$

其中，若子数组的和对 $k$ 取余数为零，则认为该子数组满足条件。
对于以 $i$ 结尾长度为 $len$ 的子数组的和：
$s[i] - s[i - len]$，如果 $s[i] - s[i - len] \bmod k = 0$，那么有：
$s[i] \bmod k = s[i - len] \bmod k$.

那么我们可以遍历前缀和数组，统计以每一位结尾的子数组的和模 $k$ 的数量，如果重复，则之前存在过一个子数组它的和与以当前数结尾的子数组的和模 $k$ 相等。即二者之差模 $k$ 为 $0$，即这个区间是一个 $k$ 倍区间。

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 100010;
int64_t a[N], s[N];
int cnt[N];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    // prefix sum
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + a[i];
    }
    
    int64_t res = 0;
    cnt[0]++;                       // s[0] % k，对应s[0]~s[i]长度为i的子区间
    for (int i = 1; i <= n; i++) {
        res += cnt[s[i] % k];       // 如果以当前i结尾的子连续数组对k的余数>0，即之前出现过相同的余数，那么当前的s[i] % k 必然和之前的某个值相同。
        cnt[s[i] % k] ++;
    }
    cout << res << endl;
    return 0;
}

注意前缀和数组中的值最高可以取到 $10^5 \times 10^5 = 10^{10}$，会爆 int。故使用 long long 来存。
另外，最高会产生 $\frac{(N + 1) \times N}{2}$ 个 $k$ 倍子数组。大概等于 $\frac{10^{10}}{2}$，也会爆 int，故答案也需要 long long 来存。

原题链接： AcWing 1230. K倍区间