CF2276C Subarrays

Monocarp 有一个包含 $n$ 个正整数的数组 $a$。他还有一个最喜欢的整数 $k$（$k < n$）。 数组中从第 $l$ 个到第 $r$ 个（$1 \leq l \leq r \leq n$）的连续元素组成的序列称为子数组。如果一个子数组满足以下两个条件，Monocarp 把它称作 $k$-平衡子数组： - 该子数组的所有元素之和可以被 $k$ 整除； - 该子数组的长度严格大于 $k$（即 $r-l+1 > k$）。 请帮 Monocarp 计算数组 $a$ 中 $k$-平衡子数组的总数。

第一行为一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的个数。 接下来是 $t$ 个测试用例。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \leq k < n \leq 2 \times 10^5$）——数组 $a$ 的元素个数和整数 $k$。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——数组 $a$ 的元素。 额外输入约束： - 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示数组 $a$ 中 $k$-平衡子数组的个数。

在第一个样例测试中，满足条件的子数组有： 1. $[2,1,3]$（所有元素之和 $2+1+3=6$ 能被 $2$ 整除）； 2. $[3,1,4]$（所有元素之和 $3+1+4=8$ 能被 $2$ 整除）。 在第二个样例测试中，所有元素均为 $1$，且 $k=3$。满足条件的子数组长度是 $6$ 和 $9$：长度为 $6$ 的子数组有四个，长度为 $9$ 的子数组有一个，所以答案是 $5$。 在第三个样例测试中，唯一长度严格大于 $3$ 的子数组是整个数组，它的元素和为 $22$，不能被 $3$ 整除，所以答案为 $0$。 由 ChatGPT 5 翻译