CF2276C.Subarrays
普及-
通过率:0%
时间限制:2.00s
内存限制:512MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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.
Monocarp 有一个由 n 个正整数组成的数组 a。他还拥有一个最喜欢的整数 k(满足 k<n)。
数组中从索引 l 到 r(1≤l≤r≤n)的连续元素序列称为一个子数组。Monocarp 将满足以下条件的子数组称为 k-平衡子数组:
- 子数组 a[l..r] 中所有元素之和能被 k 整除;
- 该子数组的长度严格大于 k(即 r−l+1>k)。
请帮助 Monocarp 计算数组 a 中 k-平衡子数组的总数。
输入格式
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.
第一行包含一个整数 t(1≤t≤104)—— 测试用例的数量。
接下来是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 k(1≤k<n≤2⋅105)—— 分别表示数组 a 的元素个数和数值 k。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an(1≤ai≤109)—— 数组 a 的元素。
输入的额外约束条件:
- 所有测试用例的 n 值之和不超过 2⋅105。
输出格式
For each test case, print one integer — the number of k-balanced subarrays in the array a.
对于每个测试用例,输出一个整数——数组 a 中 k-平衡子数组的个数。
输入输出样例
输入#1
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
输出#1
2 5 0
说明/提示
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.
在示例的第一个测试用例中,满足条件的子数组有:
- [2,1,3](所有元素之和 2+1+3=6 能被 2 整除);
- [3,1,4](所有元素之和 3+1+4=8 能被 2 整除)。
在第二个测试用例中,所有元素均为 1,且 k=3。满足条件的子数组长度为 6 和 9:长度为 6 的子数组有 4 个,长度为 9 的子数组有 1 个,因此答案为 5。
在第三个测试用例中,唯一长度严格大于 3 的子数组是整个数组。其元素和为 22,不能被 3 整除,因此答案为 0。
输入解题思路,AI测评打分。不知道怎么写?