97314 - 天平（balance）

小B在学校科技节上参加了一个天平游戏。桌上有 $n$ 块石头，编号为 $1,2,\ldots,n$ 。每块石头都被涂成红色或蓝色，第 $i$ 块石头的重量为 $a_i$ 。

小B先从桌上恰好拿走一块红色石头和一块蓝色石头，再从剩下的石头中选出最重的 $k$ 块，放入天平左边的托盘，其余石头全部放入天平右边的托盘。如果两个托盘中石头的总重量相差不超过 $\Delta$ ，这次选择就符合游戏要求。

请计算有多少种拿走石头的方案符合要求。两种方案只要拿走的石头编号不完全相同，就算作不同的方案。

如果有多块石头重量相同，使得最重的 $k$ 块石头有不止一种选法，可以任意采用其中一种选法。不同的选法不会改变两个托盘中石头的总重量，因此不另外计数。

输入

第一行包含一个整数 $T$ ，表示数据组数。

输出

对于每组数据，输出一行，包含一个整数，表示符合游戏要求的方案数量。

样例

提示

样例解释

第 1 组数据中，只有 6 号石头是蓝色，因此拿走的两块石头中必须包含 6 号石头。

拿走 5 号石头和 6 号石头后，剩下的四块石头重量均为 $1$ 。两个托盘中各放两块石头，总重量都为 $2$ ，符合要求。如果拿走任意一块重量为 $1$ 的红色石头和 6 号石头，剩下的四块石头重量为 $1,1,1,2$ 。左边托盘中最重的两块石头总重量为 $3$ ，右边托盘中的石头总重量为 $2$ 。本组数据要求两个托盘中的石头总重量完全相等，因此这种选择不符合要求。只有拿走 5 号石头和 6 号石头的方案符合要求，答案为 $1$ 。

第 2 组数据与第 1 组数据使用相同的石头，只把 $\Delta$ 从 $0$ 改为 $1$ 。此时，拿走任意一块红色石头和 6 号石头，两个托盘中石头的总重量都相差不超过 $1$ 。共有五块红色石头，因此答案为 $5$ 。

第 3 组数据中，拿走 1 号石头和 2 号石头后，剩下的两块石头重量均为 $2$ ；拿走 3 号石头和 4 号石头后，剩下的两块石头重量均为 $1$ 。这两种方案都符合要求。其他拿走一块红色石头和一块蓝色石头的方案，会剩下一块重量为 $1$ 的石头和一块重量为 $2$ 的石头，不符合要求，因此答案为 $2$ 。

数据范围与测试点

对于所有数据，保证 $1\le T\le100$ ， $4\le n\le2\times10^5$ ， $1\le k\le n-3$ ， $1\le a_i\le10^9$ ， $c_i\in{0,1}$ ， $0\le\Delta\le10^{15}$ 。同一输入文件中，所有数据组的 $n$ 之和不超过 $2\times10^5$ 。

下表中的限制对对应测试点中的每组数据均成立。“—”表示除上述通用数据范围外，没有额外限制。

测试点编号	$n$	$T$	特殊性质	分值
1	$n\le60$	$T\le20$	—	5
2	$n\le60$	$T\le20$	—	5
3	$n\le3000$	$T\le10$	—	5
4	$n\le3000$	$T\le10$	—	5
5	$n\le3000$	$T\le10$	—	5
6	$n\le3000$	$T\le10$	—	5
7	—	—	A	5
8	—	—	A	5
9	—	—	B、C	5
10	—	—	B、C	5
11	—	—	B	5
12	—	—	B	5
13	—	—	C	5
14	—	—	C	5
15	—	—	—	5
16	—	—	—	5
17	—	—	—	5
18	—	—	—	5
19	—	—	—	5
20	—	—	—	5

特殊性质 A：对于所有 $1\le i\le n$ ，均有 $a_i\in{1,2}$ 。

特殊性质 B： $k=1$ 。

特殊性质 C： $\Delta=0$ 。

同一行列出的多个特殊性质同时成立。每个测试点单独计分，每个测试点为 5 分，总分为 100 分。一个测试点输入文件中的所有数据组均回答正确时，获得该测试点的分值。

天平（balance）

题目描述

输入

输出

样例

提示

样例解释

数据范围与测试点

来源