小红的最大中位数

[题目链接](https://www.nowcoder.com/practice/daaf3691ed1c4fa49b1bf38821b1348d)

思路

给定一个长度为 $n$ 的数组，要求选出一个非空子序列，使其中位数尽可能大，并统计能取到最大中位数的子序列数量。奇数长度子序列的中位数为排序后正中间的数，偶数长度子序列的中位数为排序后中间两个数的平均值。答案对 $10^9+7$ 取模。

最大中位数是什么？

设数组的最大值为 $M$ 。任何只包含 $M$ 的子序列，中位数显然就是 $M$ 。而任何子序列的中位数都不可能超过 $M$ （因为所有元素 $\le M$ ），所以最大中位数一定等于数组的最大值 $M$ 。

哪些子序列的中位数等于 $M$ ？

设子序列长度为 $\text{len}$ ，其中包含 $j$ 个值为 $M$ 的元素和 $s$ 个值小于 $M$ 的元素。将子序列排序后，前 $s$ 个位置是小于 $M$ 的元素，后 $j$ 个位置都是 $M$ 。

奇数长度 $\text{len} = 2k+1$ ：中位数在第 $k+1$ 个位置，需要该位置是 $M$ ，即 $s \le k$ ，等价于 $s < j$ 。
偶数长度 $\text{len} = 2k$ ：中位数是第 $k$ 和第 $k+1$ 个位置的平均值，要等于 $M$ 则两个位置都必须是 $M$ ，即 $s \le k-1$ ，同样等价于 $s < j$ 。

因此条件统一为：选出的 $M$ 的个数严格大于非 $M$ 的个数，即 $j > s$ 。

计数

设数组中 $M$ 出现 $\text{cnt}$ 次，其余元素有 $\text{rest} = n - \text{cnt}$ 个。答案为：

$ $\text{ans} = \sum_{j=1}^{\text{cnt}} \binom{\text{cnt}}{j} \sum_{s=0}^{\min(j-1,\,\text{rest})} \binom{\text{rest}}{s}$ $

记 $S(k) = \sum_{s=0}^{k} \binom{\text{rest}}{s}$ ，则答案变为 $\sum_{j=1}^{\text{cnt}} \binom{\text{cnt}}{j} \cdot S(\min(j-1,\,\text{rest}))$ 。

分两段计算：

$j = 1$ 到 $\min(\text{rest},\,\text{cnt})$ ：此时 $j-1 < \text{rest}$ ，逐步递推 $S(j-1)$ 。每次 $S(j) = S(j-1) + \binom{\text{rest}}{j}$ ，增量计算即可。
$j = \text{rest}+1$ 到 $\text{cnt}$ （若 $\text{cnt} > \text{rest}$ ）：此时 $S(\text{rest}) = 2^{\text{rest}}$ ，贡献为 $2^{\text{rest}} \cdot \sum_{j=\text{rest}+1}^{\text{cnt}} \binom{\text{cnt}}{j}$ 。后者可用 $2^{\text{cnt}} - \sum_{j=0}^{\text{rest}} \binom{\text{cnt}}{j}$ 计算。

样例演示

数组 $[1, 2, 2]$ ，最大值 $M = 2$ ， $\text{cnt} = 2$ ， $\text{rest} = 1$ 。

$j$	$s$ 的范围	方案数
1	$s = 0$	$\binom{2}{1} \times \binom{1}{0} = 2$
2	$s \in \{0, 1\}$	$\binom{2}{2} \times (\binom{1}{0} + \binom{1}{1}) = 2$

合计 $2 + 2 = 4$ 。

复杂度分析

时间复杂度： $O(n)$ ，预处理阶乘和逆元后，枚举 $j$ 的循环总量为 $O(n)$ 。
空间复杂度： $O(n)$ ，存储阶乘数组。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

long long power(long long a, long long b, long long mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    int M = *max_element(a.begin(), a.end());
    int cnt = 0;
    for (int x : a) if (x == M) cnt++;
    int rest = n - cnt;

    int maxn = n + 1;
    vector<long long> fac(maxn), inv_fac(maxn);
    fac[0] = 1;
    for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % MOD;
    inv_fac[maxn - 1] = power(fac[maxn - 1], MOD - 2, MOD);
    for (int i = maxn - 2; i >= 0; i--) inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;

    auto C = [&](int n, int k) -> long long {
        if (k < 0 || k > n) return 0;
        return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
    };

    long long ans = 0;

    // 第一段：j = 1 到 min(rest, cnt)，递推前缀和 S(j-1)
    long long prefS = 1; // S(0) = C(rest, 0) = 1
    for (int j = 1; j <= min(rest, cnt); j++) {
        ans = (ans + C(cnt, j) * prefS) % MOD;
        prefS = (prefS + C(rest, j)) % MOD;
    }

    // 第二段：j = rest+1 到 cnt，内层和 = 2^rest
    if (cnt > rest) {
        long long pow2rest = power(2, rest, MOD);
        long long sumC = 0;
        for (int j = 0; j <= rest; j++) {
            sumC = (sumC + C(cnt, j)) % MOD;
        }
        long long total = (power(2, cnt, MOD) - sumC + MOD) % MOD;
        ans = (ans + total * pow2rest) % MOD;
    }

    printf("%lld\n", ans);
    return 0;
}

import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007;

    static long power(long a, long b, long mod) {
        long res = 1;
        a %= mod;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int M = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            M = Math.max(M, a[i]);
        }
        int cnt = 0;
        for (int x : a) if (x == M) cnt++;
        int rest = n - cnt;

        int maxn = n + 1;
        long[] fac = new long[maxn];
        long[] invFac = new long[maxn];
        fac[0] = 1;
        for (int i = 1; i < maxn; i++) fac[i] = fac[i - 1] * i % MOD;
        invFac[maxn - 1] = power(fac[maxn - 1], MOD - 2, MOD);
        for (int i = maxn - 2; i >= 0; i--) invFac[i] = invFac[i + 1] * (i + 1) % MOD;

        long ans = 0;

        long prefS = 1;
        int limit = Math.min(rest, cnt);
        for (int j = 1; j <= limit; j++) {
            long cntJ = fac[cnt] % MOD * invFac[j] % MOD * invFac[cnt - j] % MOD;
            ans = (ans + cntJ * prefS) % MOD;
            long cRestJ = fac[rest] % MOD * invFac[j] % MOD * invFac[rest - j] % MOD;
            prefS = (prefS + cRestJ) % MOD;
        }

        if (cnt > rest) {
            long pow2rest = power(2, rest, MOD);
            long sumC = 0;
            for (int j = 0; j <= rest; j++) {
                long c = fac[cnt] % MOD * invFac[j] % MOD * invFac[cnt - j] % MOD;
                sumC = (sumC + c) % MOD;
            }
            long total = (power(2, cnt, MOD) - sumC + MOD) % MOD;
            ans = (ans + total * pow2rest) % MOD;
        }

        System.out.println(ans);
    }
}

小红的最大中位数

小红的最大中位数

思路

最大中位数是什么？

哪些子序列的中位数等于 ？

计数

样例演示

复杂度分析

代码

哪些子序列的中位数等于 $M$ ？