1.K倍区间
1.题目描述
一个整数序列 A = ( a 1 , a 2 , ⋯ , a n ) A=(a_1 ,a_2,⋯,a_n) A=(a1,a2,⋯,an)的区间和为 S i , j = a i + a i + 1 + ⋯ + a j 。 S_{i,j} =a_i +a_{i+1} +⋯+a_j 。 Si,j=ai+ai+1+⋯+aj。
给定整数序列 A A A 和一个正整数 k k k, 请问有多少个区间 [ i , j ] [i,j] [i,j]满足
1 ≤ i ≤ j ≤ n 1≤i≤j≤n 1≤i≤j≤n且 S i , j S_{i,j} Si,j 是 k k k 非负整数倍。
2.输入格式
输入的第一行包含两个整数 n 、 k n、k n、k, 用一个空格分隔。
第二行包含 n n n 个整数 a 1 , a 2 , ⋯ , a n a_1 ,a_2 ,⋯,a_n a1,a2,⋯,an , 相邻的整数之间用一个空格分隔。
3.输出格式
输出一行包含一个数表示满足条件的区间数量。
4.样例输入
7 3
1 -1 0 2 2 2 -30
5.样例答案
7
6.数据范围
1 ≤ n ≤ 100000 , 1 ≤ k ≤ 1 0 9 , − 1 0 9 ≤ a i ≤ 1 0 9 1≤n≤100000,1≤k≤10^9,−10^9≤ai≤10^9 1≤n≤100000,1≤k≤109,−109≤ai≤109
7.原题链接
2.解题思路
本题为原K倍区间的升级版，范围不仅变大且增加了负数，由于需要求得k的非负整数倍，我们需要进行分类讨论。
先求得数组 a a a 的前缀和数组 s s s，研究一段区间和是否为 k k k倍区间，其实本质就是求多少对下标 i , j i,j i,j 满足 ( s [ j ] − s [ i ] ) % k = = 0 (s[j]-s[i])\%k==0 (s[j]−s[i])%k==0，当然需要满足 0 ≤ i < j ≤ n 0\leq i <j \leq n 0≤i<j≤n。
我们从 s [ i ] s[i] s[i]和 s [ j ] s[j] s[j]的奇偶性去进行分类讨论：
-
当 s [ i ] ≥ 0 s[i]\geq0 s[i]≥0 且 s [ j ] ≥ 0 s[j] \geq 0 s[j]≥0
显然这种情况如果满足 a [ j ] % k = a [ i ] % k a[j]\%k=a[i]\%k a[j]%k=a[i]%k，也就是说两者对 k k k 的余数相同则说明我们找到了一对符合的下标，当然还得满足 s [ i ] ≤ s [ j ] s[i]\leq s[j] s[i]≤s[j]。 -
当 s [ i ] < 0 s[i]<0 s[i]<0 且 s [ j ] ≥ 0 s[j] \geq 0 s[j]≥0
显然此时 s [ j ] − s [ i ] s[j]-s[i] s[j]−s[i]一定是一个非负数，是有可能作为答案的，这种一正一负的情况显然不应该满足且不会满足 a [ j ] % k = a [ i ] % k a[j]\%k=a[i]\%k a[j]%k=a[i]%k。那么满足什么条件是合法的呢？显然手推一下可以发现如果满足
s [ j ] % k − k = s [ i ] % k s[j]\%k-k=s[i]\%k s[j]%k−k=s[i]%k
那么 i , j i,j i,j 也是一对合法区间。 -
当 s [ i ] ≥ 0 s[i]\geq0 s[i]≥0 且 s [ j ] < 0 s[j]<0 s[j]<0
显然 s [ j ] − s [ i ] s[j]-s[i] s[j]−s[i]一定为负数，一定不合法。 -
当 s [ i ] ≤ 0 s[i]\leq0 s[i]≤0 且 s [ j ] ≤ 0 s[j]\leq0 s[j]≤0
如果此时满足 s [ i ] < s [ j ] s[i]<s[j] s[i]<s[j] 且满足 s [ j ] % k = s [ i ] % k s[j]\%k=s[i]\%k s[j]%k=s[i]%k，那么 i , j i,j i,j符合要求。
经过讨论，显然我们必须做的一件事是需要将数组 s s s 按照对 k k k 的余数来进行分组。对于任意一组数 v v v，无论里面存的是负数还是正数，有多少对数满足 i < j i<j i<j 且 v [ i ] ≤ v [ j ] v[i]\leq v[j] v[i]≤v[j] 则有多少答案，这个过程我们可以使用树状数组求解，但由于 v [ i ] v[i] v[i] 有可能特别大，每组数我们都需要先进行离散化处理。
分析中比较特殊的是第二种情况，对于每个非负的 s [ j ] s[j] s[j]，我们还需要找到在它之前出现过多少个负数 s [ i ] s[i] s[i]，满足 s [ j ] % k − k = s [ i ] % k s[j]\%k-k=s[i]\%k s[j]%k−k=s[i]%k。那么我们还需要去分组存下标，然后去对应的组里二分去找一下有多少个 i i i 符合即可。
具体实现见代码。
3 Ac_code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;
int n, k;
template <typename T>
struct BIT {
const int n;
std::vector<T> a;
BIT(int n) : n(n), a(n) {
}
void add(int x, T v) {
for (int i = x; i <= n; i += i & -i) {
a[i - 1] += v;
}
}
T sum(int x) {
T ans = 0;
for (int i = x; i > 0; i -= i & -i) {
ans += a[i - 1];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l);
}
};
void solve()
{
cin >> n >> k;
std::vector<LL> s(n + 1);
map<int, std::vector<LL>> m;
map<int, std::vector<int>> e;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
s[i] += s[i - 1];
}
for (int i = 0; i <= n; ++i) {
m[s[i] % k].push_back(s[i]);
e[s[i] % k].push_back(i);
}
LL ans = 0;
for (auto [x, y] : m) {
auto arr = y;
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
BIT<int> tr(arr.size() + 1);
if (x >= 0) {
//正数减去正数
for (auto v : y) {
int t = lower_bound(arr.begin(), arr.end(), v) - arr.begin() + 1;
ans += tr.sum(t);
tr.add(t, 1);
}
//正数减去负数
for (auto v : e[x]) {
ans += upper_bound(all(e[x - k]), v) - e[x - k].begin();
}
} else {
//负数减去负数
for (auto v : y) {
int t = lower_bound(arr.begin(), arr.end(), v) - arr.begin() + 1;
ans += tr.sum(t);
tr.add(t, 1);
}
}
}
cout << ans << '\n';
}
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 1;
while (t--)
{
solve();
}
return 0;
}
转载：https://blog.csdn.net/m0_57487901/article/details/128823011