题解 | 中位数之和

思路是先对二进制序列进行排序，然后计算每个元素被选做中位数的次数，将次数乘元素值进行求和。

次数的计算，则是考虑从该元素的左右各选择m个数，m=(k-1)//2，左边记为left，右边记为right。总共就有left*right种可能，也就是会被选中这么多次。

MOD = 10**9 + 7
MAXN = 2 * 10**5 + 10

# 预处理阶乘和逆元
fac = [1] * MAXN
inv = [1] * MAXN
for i in range(1, MAXN):
    fac[i] = fac[i - 1] * i % MOD
inv[MAXN - 1] = pow(fac[MAXN - 1], MOD - 2, MOD)
for i in range(MAXN - 2, -1, -1):
    inv[i] = inv[i + 1] * (i + 1) % MOD

def C(n, k):
    if k < 0 or k > n:
        return 0
    return fac[n] * inv[k] % MOD * inv[n - k] % MOD

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    lst = list(map(int, input().split()))
    # 对二进制序列进行排序
    lst.sort()
    # 计算每个子序列中间元素的左右两边各有多少元素
    m = (k - 1) // 2
    res = 0
    # 保证左右都能取 m 个
    for i in range(m, n - m):
        # 左边从i个中挑m个
        left = C(i, m)
        # 右边从n-i-1中挑n个
        right = C(n - i - 1, m)
        # 计算这个数被挑做中位数的次数
        total = left * right % MOD
        # 计算结果
        res = (res + lst[i] * total) % MOD
    print(res)