C. Subarrays

来源：Codeforces ★ 1300

本题活力0.64按难度、完成结果与训练证据估算

算法如山行则将至

题目描述

C. Subarrays
time limit per test2 seconds
memory limit per test512 megabytes
Monocarp has an array a
consisting of n
positive integers. He also has a favorite integer k
(k<n
).

A sequence of consecutive elements of the array with indices from l
to r
(1≤l≤r≤n
) is called a subarray. Monocarp calls a subarray k
-balanced if the following conditions hold:

the sum of all elements in the subarray from l
to r
inclusive is divisible by k
;
the length of this subarray is strictly greater than k
(that is, r−l+1>k
).
Help Monocarp determine the total number of k
-balanced subarrays in the array a
.

Input
The first line contains an integer t
(1≤t≤104
) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains two integers n
and k
(1≤k<n≤2⋅105
) — the number of elements in the array a
and the number k
.

The second line of each test case contains n
integers a1,a2,…,an
(1≤ai≤109
) — the elements of the array a
.

Additional constraints on the input:

the sum of n
over all test cases does not exceed 2⋅105
.
Output
For each test case, print one integer — the number of k
-balanced subarrays in the array a
.

Example
InputCopy
3
5 2
2 1 3 1 4
9 3
1 1 1 1 1 1 1 1 1
4 3
2 8 5 7
OutputCopy
2
5
0
Note
In the first test case of the example, the suitable subarrays are:

[2,1,3]
(the sum of all elements 2+1+3=6
is divisible by 2
);
[3,1,4]
(the sum of all elements 3+1+4=8
is divisible by 2
).
In the second test case, all elements are equal to 1
, and k=3
. The suitable subarrays have lengths 6
and 9
: there are four subarrays of length 6
and one subarray of length 9
, so the answer is 5
.

In the third test case, the only subarray of length strictly greater than 3
is the entire array. Its sum is 22
, which is not divisible by 3
, so the answer is 0
.

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, k;
        cin >> n >> k;

        vector<int> pref(n + 1, 0);

        for (int i = 1; i <= n; i++) {
            long long x;
            cin >> x;
            pref[i] = (pref[i - 1] + x % k) % k;
        }

        vector<int> cnt(k, 0);
        long long ans = 0;

        for (int r = 1; r <= n; r++) {
            int j = r - k - 1;
            if (j >= 0) {
                cnt[pref[j]]++;
            }

            ans += cnt[pref[r]];
        }

        cout << ans << '\n';
    }

    return 0;
}

题目描述

思考与重做

代码