1999F.md (2087B)
1 Source: https://codeforces.com/problemset/problem/1999/F 2 3 F. Expected Median 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Arul has a binary array$^{\text{∗}}$ $a$ of length $n$. 22 23 He will take all subsequences$^{\text{†}}$ of length $k$ ($k$ is odd) of this array and find their median.$^{\text{‡}}$ 24 25 What is the sum of all these values? 26 27 As this sum can be very large, output it modulo $10^9 + 7$. In other words, print the remainder of this sum when divided by $10^9 + 7$. 28 29 $^{\text{∗}}$A binary array is an array consisting only of zeros and ones. 30 31 $^{\text{†}}$An array $b$ is a subsequence of an array $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements. Subsequences don't have to be contiguous. 32 33 $^{\text{‡}}$The median of an array of odd length $k$ is the $\frac{k+1}{2}$-th element when sorted. 34 35 Input 36 37 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 38 39 The first line of each test case contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 2 \cdot 10^5$, $k$ is odd) — the length of the array and the length of the subsequence, respectively. 40 41 The second line of each test case contains $n$ integers $a_i$ ($0 \leq a_i \leq 1$) — the elements of the array. 42 43 It is guaranteed that sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, print the sum modulo $10^9 + 7$. 48 49 Example 50 51 Input 52 53 ``` 54 8 55 56 4 3 57 58 1 0 0 1 59 60 5 1 61 62 1 1 1 1 1 63 64 5 5 65 66 0 1 0 1 0 67 68 6 3 69 70 1 0 1 0 1 1 71 72 4 3 73 74 1 0 1 1 75 76 5 3 77 78 1 0 1 1 0 79 80 2 1 81 82 0 0 83 84 34 17 85 86 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 87 ``` 88 89 Output 90 91 ``` 92 2 93 5 94 0 95 16 96 4 97 7 98 0 99 333606206 100 ``` 101 102 Note 103 104 In the first test case, there are four subsequences of $[1,0,0,1]$ with length $k=3$: 105 106 * $[1,0,0]$: median $= 0$. 107 * $[1,0,1]$: median $= 1$. 108 * $[1,0,1]$: median $= 1$. 109 * $[0,0,1]$: median $= 0$. 110 111 The sum of the results is $0+1+1+0=2$. 112 113 In the second test case, all subsequences of length $1$ have median $1$, so the answer is $5$.