Sum of medians of all subsets

Правка en2, от bihariforces, 2023-04-04 13:32:32

Let's stick to only odd-length subsets for simplicity, given an array of integers, find sum of median of all subsets mod $$$1e9 + 7$$$, median is the middle element for odd-length subsets when sorted.

First step would obviously be sorting but then to count number of subsets whose median is $$$arr[i]$$$ we need to find number of ways to pick equal number of elements from it's left and right, if left has $$$x$$$ elements and right has $$$y$$$ elements, then,

$$$ count(subsets) = \sum_{i=0}^{\min(x,y)} \binom{x}{i} \binom{y}{i} $$$

Finding this for each element would make it $$$O(N^2)$$$, is there a faster method to find the sum of binomial coefficients as shown above efficiently possibly with some precomputation? Or some entirely different approach to solve the original problem?

Теги implementations, combinatorics, binomial coefficients


  Rev. Язык Кто Когда Δ Комментарий
en2 Английский bihariforces 2023-04-04 13:32:32 29
en1 Английский bihariforces 2023-04-04 13:26:35 792 Initial revision (published)