题解：CF1999F Expected Median

GoldenCreeper · 2024-08-09 22:09:48 · 题解

注意到序列中的顺序是无关紧要的，我们只需要关注 0 和 1 的个数。

不妨设序列中有 a 个 0，b 个 1，选取后的序列中有 c 个 0，d 个 1。如果选取后的中位数为 1，那么有 c\ge\dfrac{k+1}2，此时 d = k - c，所以会对答案产生 C_k^c\times C^d_k 的贡献。

故只需计算 \sum\limits_{i=\frac{k+1}2}^kC_i^c\times C_i^d 即可，参考实现。