题意:问有多少段的和能被k整除
这个题跟我入队考试的题非常的像。
首先他问我们某一段的和是不是一个k的倍数,那么一段和我们很自然的就联想到前缀和了。而且我们知道,如果对每一个前缀和都进行%k处理,那么就一定会使得某些数是0(假设这个数的位置是i),那么就说明从1到i的所有的数的和都是k的倍数。那么我们也会得到有的和并不是0,而是1~(k - 1)中的数。但是不妨碍里面有相同的数。
假设 s[i] % k = x,那么我们有取余的定义可知:
$$
s[i] / k = n \cdots x, \\
k * n + x = s[i]
$$
那么假设还有一个数s[j]的取余结果也是x,同理
$$ k * m + x = s[j] $$
两式相减得:
$$ k \* n - k\*m=s[i]-s[j], \\ k*(n-m) = s[i]-s[j] $$
那么就可以得到:
$$ (s[i]-s[j]) / k = (n - m) \cdots 0 $$
即:
$$
(s[i]-s[j]) \% k = 0
$$
那么我们就能得到一下结论:
如果某个余数在出现过之后在它后面再次出现过,那么 [ i , j ]这个区间就可以是个k倍区间。
所以说,假设一个余数出现过 m 次,那么同时包含这个余数的k倍区间的个数就是 (m - 1) * m / 2次(因为出现的第一次无法与前面组成k倍区间)
假设出现了5次
1 2 3 4 5
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
每个位置与前面的组成答案,就是 1 + 2 + 3 + 4 + .....(n - 2) * (n -1) = (n - 1) * n / 2
当0为余数的时候,就是它出现的次数就是(m + 1) * m / 2(余数是0 的时候,第一次出现的那个位置也可以组成一个k倍区间)
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
int n;
ll a[100000 + 10];
int k;
ll s[100000 + 10]; //看数据范围我们知道,a[i]最大100000,你们到最后s[i]最大到100000 * 100000 = 10^10超出int
vector<ll> wei[100000 + 10]; //存第几位出现的,其实这里只存出现的个数就行;读者可以自行更改一下
int main(){
cin >> n >> k;
for (int i = 1; i <= n; i++){
cin >> a[i];
s[i] = (s[i - 1] % k + a[i] % k) % k;
wei[s[i]].push_back(i);
}
ll x = wei[0].size();
ll cnt = x * (x + 1) / 2;
for (int i = 1; i <= k; i++){
x = wei[i].size();
cnt += ((x - 1) * x / 2);
}
cout << cnt;
return 0;
}
其实这种做法跟y总的思路差不多,