Information
- ID
- 7
- Time
- 2000ms
- Memory
- 256MiB
- Difficulty
- —
- Tags
- # Submissions
- 16
- Accepted
- 2
- Uploaded By
假设数组中有 x 个 1 和 y 个 0。
如果长度为 k 的子序列的中位数是 1 ,那么数组中至少有 ⌊2k⌋+1 个 1。
让我们遍历从 ⌊2k⌋+1 到 x 的子序列中的 1 的个数。假设有 i 个 1。那么有 k−i 个零。从 x 中选择 i 个一的方法数是 (ix) ,即 x 选择 i (这就是所谓的二项式系数)。同样,从 y 中选择 k−i 个零的方法数是 (k−iy) 。
因此,答案就是从 ⌊2k⌋+1 到 x 的所有 i 的 (ix)(k−iy) 之和。计算二项式系数的方法有很多,例如预先计算所有阶乘,然后使用公式 (kn)=(n−k)!k!n! 。根据实现方式的不同,可能需要花费 O(nlogMOD) 或 O(n+logMOD) 的时间。
By signing up a wangzaioj universal account, you can submit code and join discussions in all online judging services provided by us.