#390. Subarrays(子数组)

Subarrays(子数组)

题目描述

昊谦 有一个由 nn 个正整数组成的数组 aa,还有一个他最喜欢的整数 kk(k<nk<n)。(什么!竟然有人真的喜欢数字😯)

对于满足 1≤l≤r≤n1\le l\le r\le n 的下标 l,rl,r,数组中从第 ll 个元素到第 rr 个元素的连续序列称为一个子数组。

如果一个子数组同时满足以下两个条件,昊谦 就称其为一个 kk-数组:

  1. 子数组的元素之和能被 kk 整除;
  2. 子数组的长度严格大于 kk,即 r−l+1>kr-l+1>k。

请你求出数组 aa 中 kk-数组的总数。

输入格式

第一行包含一个整数 tt(1≤t≤1041\le t\le 10^4),表示测试用例数。

每组测试用例包含两行:

  • 第一行包含两个整数 n,kn,k(1≤k<n≤2×1051\le k<n\le 2\times 10^5),分别表示数组长度和给定整数。
  • 第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤1091\le a_i\le 10^9)。

保证所有测试用例的 nn 之和不超过 2×1052\times 10^5。

输出格式

对每组测试用例输出一行一个整数,表示 kk-数组的数量。

注意:答案可能超过 32 位有符号整数范围。

样例

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
2
5
0

样例说明

第 1 组: 符合条件的子数组为:

  • [2,1,3][2,1,3],元素和为 66,能被 22 整除,且长度 3>23>2;
  • [3,1,4][3,1,4],元素和为 88,能被 22 整除,且长度 3>23>2。

因此答案为 22。

第 2 组: 所有元素都是 11,且 k=3k=3。符合条件的子数组长度只能为 66 或 99:长度为 66 的有 44 个,长度为 99 的有 11 个,所以答案为 55。

第 3 组: 唯一长度严格大于 33 的子数组是整个数组,但它的元素和为 2222,不能被 33 整除,因此答案为 00。

数据范围与限制

  • 时间限制:2 秒。
  • 内存限制:512 MiB。
  • 1≤t≤1041\le t\le 10^4;
  • 1≤k<n≤2×1051\le k<n\le 2\times 10^5;
  • 1≤ai≤1091\le a_i\le 10^9;
  • 每个输入文件中所有测试用例的 nn 之和不超过 2×1052\times 10^5。