小圆前辈的数组

题意：求连续子序列的满足 $\sum{a_i}\ge z, \sum a_i\% k = = 0$ 有多少个
两个条件中任意一种都很好解决
- $\sum a_i \ge z$ ，可以用前缀和优化，枚举起点，然后二分终点就可以求出序列个数
- $\sum a_i \% k == 0$ 可以前缀和取模，然后放入桶 $cnt[i]$ 中优化，结果就是 $cnt[0] + C_{cnt[0]}^{2} + C_{cnt[1]}^2 + \cdots+C_{cnt[k-1]}^2$ （也就是取 $k$ 的倍数 + 取 $prefix[i] = prefix[j]$ 的情况（此时多出来的能减掉））
当两个条件在一起的时候，我们考虑先满足一个情况，然后再去满足另外一个情况。这里先去满足 $\sum {a_i} \% k == 0$ 的情况
先将前缀和 $prefix$ 取模处理，再将其对应的前缀和的值存入桶内，即 $cnt[prefix[j] \%k]$ 中加入 $prefix[j]$ 。显然的是，在桶内数字单调递增。所以枚举起点，然后二分终点统计 $ans$

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", (x))
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

const int N = 1e5 + 7;
const int M = 2e5 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;

ll n, k, z;
ll prefix[N];
vector<ll> cnt[N];

inline ll read() {
    ll s = 0, f = 1;    
    char ch;
    do {
        ch = getchar();
        if (ch == '-') f = -1;
    } while (ch < 48 || ch > 57);
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}

signed main() {
    n = read(), k = read(), z = read();
    for(int i = 1; i <= n; ++i) {
        prefix[i] = read();
        prefix[i] += prefix[i-1];
        cnt[prefix[i] % k].push_back(prefix[i]);
    }//处理%k
    ll ans = cnt[0].end() - lower_bound(cnt[0].begin(), cnt[0].end(), z);
    for(int i = 0; i < k; ++i) {//余数
        for(int j = 0; j < cnt[i].size(); ++j) {//起始位置
            ans += cnt[i].end() - lower_bound(cnt[i].begin() + j, cnt[i].end(), z + cnt[i][j]);
        }//枚举
    }
    cout << ans << endl;
    return 0;
}

题解 | #小圆前辈的数组#

小圆前辈的数组