题解 | 中位数之和

思考点1：求中位数需要选取子序列后排序

思考点2：子序列可以是非连续的序列

思考点3：既然如此，我们只需要考虑将原数组排序，因为无论怎么选，最终排序后的结果与原序列一致。

思考点4：那说明我们只需要关心0和1的个数

现在问题变成，长度为n，且有a个1，n-a个0的数组，计算长度为k的子序列中位数之和。

假设前面选了cnt个0，后面就必选k-cnt个1。

当cnt=k/2向上取整时，说明中位数是0，否则就是1，然而中位数是0对答案并没有贡献，所以我们需要枚举cnt在k/2以前的

即

当选了0个0，后面就选k个1。有几种？

当选了1个0，后面就选k-1个1。有几种？

以此类推。

这里推荐使用乘法逆元，因为这里需要查询次组合数，

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;  // 定义LL为long long的别名
const int N = 1e6 + 10;  // 将MAXN改为N，预处理的最大范围
const int p = 1e9 + 7;
vector<LL> fact(N);   // 存储阶乘 mod p 的结果
vector<LL> inv_fact(N); // 存储阶乘的逆元 mod p 的结果

// 快速幂：计算 (base^exponent) % mod
LL quick_pow(LL base, LL exponent, LL mod) {
    LL res = 1;
    base %= mod; // 先取模，避免溢出
    while (exponent > 0) {
        if (exponent & 1) { // 指数为奇数时，结果乘上当前base
            res = (res * base) % mod;
        }
        base = (base * base) % mod; // base平方
        exponent >>= 1; // 指数除以2
    }
    return res;
}

// 预处理阶乘和阶乘逆元数组
void pre() {
    // 1. 预处理阶乘数组 fact
    fact[0] = 1; // 0! = 1
    for (int i = 1; i < N; ++i) {
        fact[i] = (fact[i-1] * i) % p;
    }

    // 2. 预处理阶乘逆元数组 inv_fact（从后往前推）
    // 先算最大数的阶乘逆元：inv_fact[N-1] = (N-1)! 的逆元
    inv_fact[N-1] = quick_pow(fact[N-1], p-2, p);
    // 递推公式：inv_fact[i] = inv_fact[i+1] * (i+1) % p
    for (int i = N-2; i >= 0; --i) {
        inv_fact[i] = (inv_fact[i+1] * (i+1)) % p;
    }
}

// 计算 C(a, b) % p
LL C(int a, int b, LL p) {
    // 边界条件：b > a 或 b < 0 时，组合数为0
    if (b < 0 || b > a) return 0;
    // 核心公式：C(a,b) = fact[a] * inv_fact[b] * inv_fact[a-b] mod p
    return fact[a] * inv_fact[b] % p * inv_fact[a - b] % p;
}



int n,k;
void solve() {
    cin >> n >> k;
    int A = 0, B = 0;
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        bool x;
        cin >> x;
        if (x) B++;
        else A++;
    }
    int z = (k + 1) / 2;
    LL tmp;
    for (int i = 0; i <= min(A, z-1); i++) { //枚举
        if (k - i <= B) {
            tmp = C(A, i, p);
            tmp = (tmp * C(B, k - i, p)) % p;
            ans = (ans + tmp ) % p;
        }

    }
    cout << ans << "\n";
    return;
}
int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    pre();
    int tt;
    cin >> tt;
    while (tt--) solve();
    return 0;
}