题目描述
题目要求求出连续区间中满足$k$倍区间的个数,包含区间本身。
使用前缀和存储连续区间总和,根据公式: $( sum[r] - sum[l - 1] ) \% k == 0$ 就符合要求了,
通过观察可发现,只需要 $sum[r] \% k == sum[l - 1] \% k$,即区间模上$k$的余数相同就可以凑一个$k$倍区间
即相同余数的区间可以两两配对形成新的k倍区间 ( 即两个$sum$值相减其剩余部分就是$k$倍区间 ),其公式是组合 $C^2_n$ 从$n$个里选两个。
$C^2_n = n * (n - 1) / 2 = 1 + 2 + 3 + … + n - 1$
样例
例子:k = 2;
[2], [4], [1,3], [1,4], [2,5], [3,5] 6个
1 2 3 4 5
sum 1 3 6 10 15
mod 1 1 0 0 1
cnt[余数] = 多少个余数相同的区间
cnt[0] = 2,
cnt[1] = 3,
组合: // sum[5] - sum[2] = 15 - 3 = 12 => 即区间[3, 5]
C3_2 = 3, : [2], [2,5], [3,5] 3个 // 从3个 mod = 1 里面挑2个进行组合
C2_2 = 1, : [4] 1个 // sum[4] - sum[3] = 10 - 6 = 4 => [4]区间
再加上 cnt[0] = 2, -> [1,3], [1,4] 2个 // 区间本身也要加上去
总计:6个
算法1
blablabla
参考文献
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
typedef long long LL;
int n, k;
LL sum[N], cnt[N];
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i ++)
{
scanf("%d", &sum[i]);
sum[i] += sum[i - 1]; // 前缀和
}
for (int i = 1; i <= n; i ++)
{
cnt[sum[i] % k] ++; // 余数相同的放在cnt[余数] ++
}
LL ans = 0;
for (int i = 0; i < k; i ++) // 因为余数只有 0~k-1 范围内
{
ans += (cnt[i] * (cnt[i] - 1)) / 2; // 从n个里选2个
}
cout << ans + cnt[0] << endl;
return 0;
}