#390. Subarrays(子数组)
Subarrays(子数组)
题目描述
昊谦 有一个由 个正整数组成的数组 ,还有一个他最喜欢的整数 ()。(什么!竟然有人真的喜欢数字😯)
对于满足 的下标 ,数组中从第 个元素到第 个元素的连续序列称为一个子数组。
如果一个子数组同时满足以下两个条件,昊谦 就称其为一个 -数组:
- 子数组的元素之和能被 整除;
- 子数组的长度严格大于 ,即 。
请你求出数组 中 -数组的总数。
输入格式
第一行包含一个整数 (),表示测试用例数。
每组测试用例包含两行:
- 第一行包含两个整数 (),分别表示数组长度和给定整数。
- 第二行包含 个整数 ()。
保证所有测试用例的 之和不超过 。
输出格式
对每组测试用例输出一行一个整数,表示 -数组的数量。
注意:答案可能超过 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 组: 所有元素都是 ,且 。符合条件的子数组长度只能为 或 :长度为 的有 个,长度为 的有 个,所以答案为 。
第 3 组: 唯一长度严格大于 的子数组是整个数组,但它的元素和为 ,不能被 整除,因此答案为 。
数据范围与限制
- 时间限制:2 秒。
- 内存限制:512 MiB。
- ;
- ;
- ;
- 每个输入文件中所有测试用例的 之和不超过 。