1 solutions

  • 1
    @ 2024-12-9 14:05:42

    假设数组中有 xx 个 1 和 yy 个 0。

    如果长度为 kk 的子序列的中位数是 11 ,那么数组中至少有 ⌊k2⌋+1\lfloor \frac{k}{2} \rfloor + 1 个 1。

    让我们遍历从 ⌊k2⌋+1\lfloor \frac{k}{2} \rfloor + 1 到 xx 的子序列中的 1 的个数。假设有 ii 个 1。那么有 k−ik - i 个零。从 xx 中选择 ii 个一的方法数是 (xi)\binom{x}{i} ,即 xx 选择 ii (这就是所谓的二项式系数)。同样,从 yy 中选择 k−ik-i 个零的方法数是 (yk−i)\binom{y}{k-i} 。

    因此,答案就是从 ⌊k2⌋+1\lfloor \frac{k}{2} \rfloor + 1 到 xx 的所有 ii 的 (xi)(yk−i)\binom{x}{i}\binom{y}{k-i} 之和。计算二项式系数的方法有很多,例如预先计算所有阶乘,然后使用公式 (nk)=n!(n−k)!k!\binom{n}{k} = \frac{n!}{(n-k)!k!} 。根据实现方式的不同,可能需要花费 O(nlog⁡MOD)\mathcal{O}(n \log \mathrm{MOD}) 或 O(n+log⁡MOD)\mathcal{O}(n + \log \mathrm{MOD}) 的时间。

    • 1

    Information

    ID
    7
    Time
    2000ms
    Memory
    256MiB
    Difficulty
    —
    Tags
    # Submissions
    16
    Accepted
    2
    Uploaded By