题解 | 中位数之和

逛了一圈发现没有我的做法，就写一个吧，详情可以参考我的b站视频******************************************

哎呀呀，这种一眼就能看出是组合数学的题目，居然还要本天才翔子出马？你们这些杂鱼的大脑难道和二进制数组里的 0 一样，完全没有存在的价值吗？呵呵~

既然你们求知欲这么旺盛（其实是太笨了吧？），那我就勉为其难地给你们这群逊毙了的家伙写篇题解。好好盯着看，这可是天才的恩赐！

📊 翔子的天才课堂：二进制中位数的秘密

🧐 核心逻辑：中位数才不是随便当的！

听好了，笨蛋杂鱼们！这道题的数组只有 0 和 1。

中位数的本质：对于长度为的子序列，中位数是 1 的充分必要条件是——这个子序列里至少有个 1。
固定中位数的策略：我们把原数组从小到大排个序（虽然里面全是 0 和 1，但排序后 0 都在左边， 1 都在右边）。
计数大法：

假设我们要让第个位置的数成为中位数。
我们需要在它的左边（个位置）选出个数。
我们需要在它的右边（个位置）选出个数。
这样总共就选了个数，且刚好在中间。
既然只有的时候才会对总和有贡献，那我们只需要算时的组合数就行了！

这种的预处理加的遍历，连杂鱼都能跑通，要是你还写错，建议直接退出代码界呢~

💻 毫无难度的 C++ 代码

这种基础的逆元和阶乘预处理，要是杂鱼不会写，翔子真的会笑出声的哦！

#include <bits/stdc++.h>
#define il inline
#define double long double
using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128 = __int128_t;

const ll N = 2e5 + 5, mod = 1e9+7, inf = 2e18;
const double eps = 1e-9;
double PI = 3.1415926;

// 杂鱼才需要写注释，但我还是帮你们写了，感谢我吧！
ll quick_mi(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

// 逆元都不会算的杂鱼可以去重修小学数学了
ll inv(ll n){
    return quick_mi(n,mod-2);
}

vector<ll>fact(N,1),inv_fact(N);

// 组合数公式 C(n, m)，杂鱼记住了吗？
ll C(ll n,ll m){
    if(m<0||m>n)return 0; // 选不出来就是0，和杂鱼的智商一样
    return fact[n]*inv_fact[m]%mod*inv_fact[n-m]%mod;
}

il void solve() {
    int n,k;
    cin>>n>>k;
    vector<ll>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    // 排序后 1 都在右边，方便我们固定中位数
    sort(a.begin()+1,a.end());
    ll ans=0;
    ll need=k/2; 
    for(int i=1;i<=n;i++){
        // 只有 a[i]=1 才有贡献，杂鱼要是这里写错就逊爆了
        (ans+=C(i-1,need)*C(n-i,need)*a[i]%mod)%=mod;
    }
    cout<<ans<<'\n';
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;

    // 预处理阶乘，为了拯救杂鱼的时间复杂度
    for(int i=1;i<N;i++){
        fact[i]=fact[i-1]*i%mod;
    }
    inv_fact[N-1]=inv(fact[N-1]);
    for(int i=N-2;i>=0;i--){
        inv_fact[i]=inv_fact[i+1]*(i+1)%mod;
    }

    cin >> t;

    while (t--){
        solve();
    }
    return 0;
}

🐍 慢吞吞的 Python 代码

虽然 Python 慢得像杂鱼爬行，但逻辑还是一样简单的呢。

import sys, math, queue, itertools, heapq
from collections import deque
from array import array
from bisect import bisect_right

# 这个递归深度，杂鱼的大脑能承受吗？
sys.setrecursionlimit(1145141919)
input = sys.stdin.readline

def read():
    line = sys.stdin.readline()
    if not line:
        return []
    return list(map(int, line.split()))

mod = 10**9 + 7
N = 2 * (10**5) + 5

def quick_mi(a, b):
    ans = 1
    while b:
        if b & 1:
            ans = ans * a % mod
        b >>= 1
        a = a * a % mod
    return ans

def inv(n):
    return quick_mi(n, mod - 2)

fact = [1] * N
inv_fact = [0] * N

def C(n, m):
    if m < 0 or m > n:
        return 0
    return fact[n] * inv_fact[m] * inv_fact[n - m] % mod

def solve():
    n, k = read()
    need = k // 2
    a = [0] + read()
    # 居然要手动排序，Python 真是麻烦呢，呵呵~
    a.sort(key=lambda x: x)
    ans = 0
    for i in range(1, n + 1):
        # 左右两边各选 need 个，中间坐个 1
        ans += a[i] * C(i - 1, need) * C(n - i, need)
        ans %= mod
    print(ans)

def main():
    # 预处理是给杂鱼最后的仁慈
    for i in range(1, N):
        fact[i] = fact[i - 1] * i % mod
    inv_fact[N - 1] = inv(fact[N - 1])
    for i in range(N - 2, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod

    line = sys.stdin.readline()
    if not line: return
    t = int(line)
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

🙄 翔子的最后嘲讽

看明白了吗？这道题的精髓就是：只要你不是个连组合数都不会算的杂鱼，你就能过！

固定中位数位置，左右两边各选一半，这么简单的逻辑要是还要我讲第二遍，我就要把你的准考证撕掉喽~ 呵呵。赶紧去提交吧，别在这里碍眼了！