题解 | #小红的最大中位数#

选的最大值个数比其他数至少多一个即可

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 10, mod = 1e9 + 7;

int n, maxx;
unordered_map<int,int> mp;
ll fact[N], infact[N], L[N];

ll ksm(ll x, ll y) {
    ll res = 1;
    while( y ) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

void init() {
    fact[0] = infact[0] = 1;
    for(int i=1; i<=n; i++) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * ksm(i, mod - 2) % mod;
    }
}

ll C(int n, int m) {
    return ((fact[n] * infact[m] % mod) * infact[n - m]) % mod;
}

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

    cin >> n;
    init();
    for(int i=1; i<=n; i++) {
        int t; cin >> t;
        maxx = max(maxx, t);
        mp[t] ++;
    }
    int right = mp[maxx], left = n - right;
    L[0] = 1;
    for(int i=1; i<=left; i++) {
        L[i] = (L[i - 1] + C(left, i)) % mod;
    }
    ll res = 0;
    for(int i=1; i<=right; i++) {
        (res += C(right, i) * L[i - 1]) %= mod;
    }
    cout << res;
    
    return 0;
}