Let \(p\) be the probability that the two options have the same number of votes at some time after \(X\) cast a vote. Then, the answer is \(1-\frac{p}{2}\), so let us find \(p\).

First, let us arrange \(K\) ESPers and \(2N+1-K\) non-ESPers in a row and fix whether each non-ESPer votes for the option with the greater number of votes at that time or the option with the less number of votes. There are \(\binom{2N+1}{K}\times 2^{2N+1-K}\) such “states”. We want to find the sum of the probabilities in all these states that X has already voted when the two options have the same number of votes for the last time.

Let us correspond to each state a sequence of length \(2N+1\) consisting of \(1\) and \(-1\) where:

• for each \(1 \leq i \leq 2N+1\), the \(i\)-th term of the sequence is \(1\) if the \(i\)-th person to vote votes for the option with the greater number of votes, and \(-1\) otherwise.

Using non-negative integers \(x\) and \(y\), we can uniquely express this sequence as:

\(S_0,-1,S_1,-1,\ldots,S_x, 1, S_{x+1}, 1, \ldots, S_{x+y}\)

where each \(S_i\) is a sequence consisting of \(1\) and \(-1\) such that every prefix sum is non-negative and the whole sum is \(0\). Note that \(S_i\) may be empty. Below, we will fix \(x\) and \(y\) and find the number of corresponding ways to choose ESPers, the average probability that \(X\) has already voted when the two options have the same number of votes for the last time, and the number of corresponding sequences \(S_0, \ldots, S_{x+y}\). Here, we note that \(x+y\) is odd since the sequence has the length of \(2N+1\).

First, \(S_0, \ldots,S_{x+y}\) have the total length of \(2N+1-x-y\), and half of their elements are \(1\), so the whole sequence contains \(\frac{2N+1-x+y}{2}\) occurrences of \(1\). Thus, there are \(\binom{\frac{2N+1-x+y}{2}}{K}\) corresponding ways to choose ESPers.

Next, consider the moment when the two options have the same number of votes for the last time if votes are actually cast according to the sequence. This will be the end of \(S_x\) if \(x\) is even, and the end of \(S_{x-1}\) if \(x\) is odd. The average number of \(1\)s from \(S_0\) through \(S_x\) is \(\frac{(x+1)(2N+1-x-y)}{2(x+y+1)}\), and the average number of \(1\)s from \(S_0\) through \(S_{x-1}\) is \(\frac{x(2N+1-x-y)}{2(x+y+1)}\). Thus, the average probability that \(X\) has already voted when the two options have the same number of votes for the last time is:

• \(\frac{(x+1)(2N+1-x-y)}{(x+y+1)(2N+1-x+y)}\) if \(x\) is even, and \(\frac{x(2N+1-x-y)}{(x+y+1)(2N+1-x+y)}\) if \(x\) is odd.

Lastly, count the corresponding \(S\). This is equal to the number of sequences of length \(2N+1\) of the form \(S_0,1,S_1,\ldots,1,S_{x+y}\), so the count is \(\binom{2N+1}{\frac{2N+1-x-y}{2}} - \binom{2N+1}{\frac{2N-1-x-y}{2}}\).

Now, let us unfix \((x, y)\). We can find the answer by summing up the following for even \(x\):

\(\binom{\frac{2N+1-x+y}{2}}{K} \times \frac{(x+1)(2N+1-x-y)}{(x+y+1)(2N+1-x+y)} \times \left(\binom{2N+1}{\frac{2N+1-x-y}{2}} - \binom{2N+1}{\frac{2N-1-x-y}{2}}\right)\)

and the following for odd \(x\):

\(\binom{\frac{2N+1-x+y}{2}}{K} \times \frac{x(2N+1-x-y)}{(x+y+1)(2N+1-x+y)} \times \left(\binom{2N+1}{\frac{2N+1-x-y}{2}} - \binom{2N+1}{\frac{2N-1-x-y}{2}}\right)\)

Now, we have a solution that works in \(O(N^2)\) time.

Let us compute the sum for even \(x\) faster. (The sum for odd \(x\) can be computed similarly, so we omit it here.)

If we fix \(x+y=2k+1\) ( \(0 \leq k \leq N\) ), only the following part of the above formula depends on \(x\):

\(\binom{\frac{2N+1-x+y}{2}}{K} \times \frac{x+1}{2N+1-x+y} = \frac{x+1}{2K} \times \binom{N+k-x}{K-1}\).

Thus, we just need to find \(\sum_{a=0}^{k} (2a+1) \binom{N+k-2a}{K-1}\) for each \(k\). By increasing \(k\) by \(2\) at a time, we can compute it with prefix sums.

Therefore, the problem can be solved in linear time.