X が投票した後のあるタイミングで、各選択肢の票数が同数となる確率を \(p\) とすると、求める確率は \(1-\frac{p}{2}\) となります。 よって、\(p\) を求めればよいです。

まず、\(K\) 人の超能力者と \(2N+1-K\) 人の非超能力者を順番に並べ、 各非超能力者について、その人が投票時に票数が多い方に投票するか、少ない方に投票するかを固定します。 状態は \(\binom{2N+1}{K}\times 2^{2N+1-K}\) 個あります。 この状態すべてにおける、最後に各選択肢の票数が同数となったときに、X が投票を終えている確率の総和、を求めればよいです。

各状態について、次の条件を満たす \(1\) と \(-1\) からなる長さ \(2N+1\) の数列を対応させます。

• 各 \(1 \leq i \leq 2N+1\) について、数列の \(i\) 項目は、\(i\) 番目に投票する人が票数の多いほうに投票するならば \(1\)、 そうでないならば \(-1\) である。

この数列は非負整数 \(x\), \(y\) を用いて以下のように一意的に表すことができます。

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

ここで、各 \(S_i\) はどの接頭和も非負であり、合計が \(0\) であるような \(1\) と \(-1\) からなる数列です。 \(S_i\) は空でもよいことに注意してください。 以下、\(x\) と \(y\) を固定して、対応する超能力者の選び方は何通りあるか、 最後に各選択肢の票数が同数となったときに X が投票を終えている確率の平均値はいくつか、 そして対応する \(S_0, \ldots,S_{x+y}\) は何通りあるかを求めます。 ただし、数列の長さが \(2N+1\) であることより \(x+y\) は奇数であることに注意します。

まず、\(S_0, \ldots,S_{x+y}\) の長さの合計は \(2N+1-x-y\) であり、そのうちの半分が \(1\) であるので、 数列には全体として \(1\) は \(\frac{2N+1-x+y}{2}\) 個含まれます。 よって、対応する超能力者の選び方は \(\binom{\frac{2N+1-x+y}{2}}{K}\) 通りです。

次に、実際にこの数列に対応する投票を行ったとき、最後に各選択肢の票数が同数となるタイミングを考えます。 これは、\(x\) が偶数のときは \(S_x\) の末尾、\(x\) が奇数のときは \(S_{x-1}\) の末尾となります。 \(S_0\) から \(S_x\) までに含まれる \(1\) の個数の平均は \(\frac{(x+1)(2N+1-x-y)}{2(x+y+1)}\) であり、 \(S_0\) から \(S_{x-1}\) までに含まれる \(1\) の個数の平均は \(\frac{x(2N+1-x-y)}{2(x+y+1)}\) です。 よって、最後に各選択肢の票数が同数となったときに X が投票を終えている確率の平均値は

• \(x\) が偶数のとき \(\frac{(x+1)(2N+1-x-y)}{(x+y+1)(2N+1-x+y)}\)、\(x\) が奇数のとき \(\frac{x(2N+1-x-y)}{(x+y+1)(2N+1-x+y)}\)

です。

最後に対応する \(S\) の個数を求めます。 これは \(S_0,1,S_1,\ldots,1,S_{x+y}\) なる長さ \(2N+1\) の列の個数と一致するので、 この個数は \(\binom{2N+1}{\frac{2N+1-x-y}{2}} - \binom{2N+1}{\frac{2N-1-x-y}{2}}\) となります。

以上をまとめると、\((x,y)\) を動かして、\(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)\)

\(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)\)

を足し合わせればよいです。これでまず \(O(N^2)\) の計算量で解くことができます。

以下、\(x\) が偶数の場合の和を求めることにします。\(x\) が奇数である場合も同様なので、ここでは省略します。

\(x+y=2k+1\) ( \(0 \leq k \leq N\) ) を固定すると、先程のうち \(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}\)

のみである。つまり、各 \(k\) について \(\sum_{a=0}^{k} (2a+1) \binom{N+k-2a}{K-1}\) が求まればよいです。 これは \(k\) の値を \(2\) ずつ増やしていくことで、累積和により求めることができます。

以上により、線形時間でこの問題を解くことができます。