#P0007. 中位数之和
中位数之和
题目描述
Waylon 有一个二进制数组 ,它的长度为 。
他将取该数组长度为 ( 为奇数)的所有子序列 ,并求出它们的中位数 。
所有这些值的和是多少?
由于这个和可能非常大,因此输出它的模数 。换句话说,输出这个数除以 的余数。
输入格式
第一行包含一个整数 ( )--测试用例数。
每个测试用例的第一行包含两个整数 和 ( , 为奇数),分别是数组的长度和子序列的长度。
每个测试用例的第二行包含 个整数 ( ) - 数组 的元素。
保证所有测试用例中 的总和不超过 。
输出格式
对于每个测试用例,输出所有可能的中位数的总和,对 取模。
样例 #1
样例输入 #1
8
4 3
1 0 0 1
5 1
1 1 1 1 1
5 5
0 1 0 1 0
6 3
1 0 1 0 1 1
4 3
1 0 1 1
5 3
1 0 1 1 0
2 1
0 0
34 17
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
样例输出 #1
2
5
0
16
4
7
0
333606206
提示
一个二进制数组是一个只由 0 和 1 组成的数组。
如果 可以从 中删除几个元素(可能是零,也可能是全部元素),那么数组 就是数组 的子序列。子序列不必是连续的。
长度为奇数 的数组的中位数是排序后的第 个元素。
在第一个测试用例中,有四个长度为 的 的子序列:
- :中位数 。
- :中位数 。
- :中位数 。
- :中位数 。
结果之和为 。
在第二个测试案例中,所有长度为 的子序列的中位数为 ,因此答案为 。