推导
$1≤N,K≤100000$
$1≤A_{i}≤100000$
预处理前缀和
//预处理前缀和
for(int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
注意到,$A.length=N$ ($A$ 的长度为$N$),所以,$1≤a[i]≤N*A_{i}≤10^{10} $。
因此,$a[i]$ 的类型为 $long$ $long$ , 使用 $int$ 会爆炸。
未经优化的普通做法 (时间复杂度 $o(n^{2})$)
会TLE,只能通过6个数据。
#include<iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, k;
LL a[N];
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
// cout << a[i] << " ";
}
LL ans = 0;
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
if((a[j] - a[i - 1]) % k == 0) ans++;
}
}
cout << ans << endl;
return 0;
}
上述代码的关键在于这里:
(a[j] - a[i - 1]) % k == 0
目的是判断$[i, j]$的区间和是否是$k$ 的倍数。
接下来,我们考虑如何优化这段代码:
a[j] % k == a[i - 1] % k
因此,前缀和数组 $a[i]$ 只需找到 $mod$ $k$ 的值相同即可。
我们将余数记为 $rm$ ,
$rm = a[i]$ $mod$ $k$ 且 $rm\in [0, k-1]$ ,$rm 为整数$ 。
我们只需要统计相同的 $rm$ 有多少对即可。
假设 $rm=p$ , $p\in [0, k - 1] $ 。
$rm=p$ 出现第 1 次为 0 对。
$rm=p$ 出现第 2 次为 0 + 1 对。
$rm=p$ 出现第 3 次为 0 + 1 + 2 对。
.
.
.
$rm=p$ 出现第 n 次为 0 + 1 + 2 + … + n - 1 对。
因此, $rm=p$ 一共有 $\frac{n * (n - 1)}{2} $ 对。
所以说,我们只需统计有多少对这样的 $rm$ 即可。
这里需要注意的是,当 $rm = 0$ 时,所对应的 $a[i]$ 单独就是 $k$ 的倍数。所以说,最终的答案还需要加上 $rm = 0$ 的个数。
当所有的 $rm = 0$ 时,最终的k倍区间个数最大,为 $\frac{n * (n + 1)}{2} $ 。所以说,区间个数最大为 $10^{10} $ , 所以答案需要用 $long$ $long$ 来存。
优化后的正确做法 (时间复杂度 $o(n)$)
#include<iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 15;
int n, k;
LL a[N];
int res[N];
int main() {
cin >> n >> k;
//预处理前缀和
for(int i = 1; i <= n; i++) {
cin >> a[i];
a[i] += a[i - 1];
}
LL ans = 0;//存最终答案
int rm = 0;//存取模后的余数
for(int i = 1; i <= n; i++) {
rm = a[i] % k;
ans += res[rm];
res[rm]++;
}
cout << ans + res[0] << endl;
return 0;
}