ここでは、形式的冪級数を用いた別解を紹介します。 本解と同様、X が投票した後のあるタイミングで、各選択肢の票数が同数となる確率を求めます。

\(xy\) 座標平面を考え、各格子点 \((x,y)\) ( \(x, y \geq 0\) ) を、一方の選択肢に \(x\) 票、 もう一方の選択肢に \(y\) 票入った状態に対応させます。 各投票は、\((0,0)\) から \(x+y=2N+1\) 上のある格子点への長さ \(2N+1\) のパスに対応します。 そのパスに使われている線分のうち \(\max\{x,y\}\) が増加する方向の線分を \(K\) 個選び、 それらが超能力者によって投票されたものとします。 このとき、実際にこの投票が行われる確率は、\(K\) 個の線分のうち \(x=y\) と共通部分をもたないものを \(s\) 個として

\(2^s / \left(\binom{2N+1}{K}\times 2^{2N+1}\right)\)

となります。 よって、選ばれた \(K\) 個の線分のうち、その線分を通った後パスが \(x=y\) と交わるものの個数を \(t\) として、 \(t \times 2^s\) の総和を求めればよいです。

ここで、\(x, y \geq 0\) 内の格子点を端点とするような長さ \(1\) の線分に対して、次のように \(w\) を変数とする多項式を割り当てます：

• その線分の \((0,0)\) に近いほうの端点が \(x=y\) 上にあるならば \(1+w\) を割り当てる。
• その線分が \((0,0)\) からみて \(\max\{x,y\}\) が増加する方向の線分であれば \(1+2w\) を割り当てる。
• その線分が \((0,0)\) からみて \(\max\{x,y\}\) が変化しない方向の線分であれば \(1\) を割り当てる。

\(2\) つの格子点 \(X\), \(Y\) を固定します。そして、\(X\) から \(Y\) へのすべてのパスに対し、そのパス上の各線分に対する多項式の積をとり、 その積の総和として得られる多項式を考えます。 このとき、この多項式の \(w^k\) の係数は、\(X\) に対応する投票の状態から \(Y\) に対応する投票の状態までの遷移であって、 その間に超能力者が \(k\) 人投票した遷移すべてに対して \(2^s\) を足し合わせた値となっています （\(s\) は \(x=y\) 上でない状態から投票を行った超能力者の人数。） この事実を用いると、次のようにして求める総和が計算できます。

\(i+j+k=N-1\) となるよう非負整数 \(i\), \(j\), \(k\) を動かし、以下のように多項式 \(P_i(w)\), \(Q_j(w)\), \(R_k(w)\) を構成します。

• \((0,0)\) から \((i,i)\) までのすべてのパスに対し、そのパス上の各線分に対する多項式の積をとり、その積の総和として得られる多項式を \(P_i(w)\) とする。
• \((0,0)\) から \((j+1,j+1)\) までの \(x=y\) を始点・終点以外で通らないすべてのパスに対し、 同様に積をとった値の総和として得られる多項式を \(Q_j(w)\) とする。
• \((0,0)\) からの長さ \(2k+1\) のすべてのパスに対し、 同様に積をとった値の総和として得られる多項式を \(R_k(w)\) とする。

\(l+m+n=K\) となるよう非負整数 \(l\), \(m\), \(n\) を動かし、 \(P_i(w)\) の \(w^l\) の係数を \(p\)、\(wQ'_j(w)\) の \(w^m\) の係数を \(q\)、そして \(R_k(w)\) の \(w^n\) の係数を \(r\) として、 \(pqr\) を足し合わせた値が求める値となります。 \(wQ'_j\) の \(w^m\) の係数とは結局、\(Q_j\) の \(w^m\) の係数に \(m\) を掛けたものであることに注意してください。

ここで、\(P(z,w) = \sum_{i\geq 0} z^iP_i(w)\), \(Q(z,w) = \sum_{j \geq 0} z^j Q_j(w)\), \(R(z,w) = \sum_{k \geq 0} z^k R_k(w)\) という \(2\) 変数形式的冪級数を考えます。 先程の考察より、\((P(\partial_w Q)R)(z,w)\) の \(z^{N-1}w^{K-1}\) の係数が求める値です。 以下、\(P\), \(Q\), \(R\) の値を具体的に計算します。

まず \(R\) を計算します。\(R_k(w)=(2+2w)^{2k+1}\) なので、

\(R(z,w)=\sum_{k \geq 0} 2(1+w)\{4z(1+w)^2\}^k = \frac{2(1+w)}{1-4z(1+w)^2}\)

となります。

次に \(Q\) を計算します。\(c_j\) を \(j\) 番目の Catalan 数とすると \(Q_j(w)=2c_j(1+w)(1+2w)^j\) なので、

\(g(z)=\sum_{j \geq 0} c_j z^j = \frac{1-\sqrt{1-4z}}{2z}\)

を用いると

\(Q(z,w)=\sum_{j \geq 0} 2c_j(1+w)\{z(1+2w)\}^j = 2(1+w)g(z(1+2w))\)

となります。

最後に \(P\) を計算します。\((0,0)\) から \((i,i)\) までのパスを \(x=y\) を通る回数で分類することで

\(P(z,w)=1+zQ(z,w)+(zQ(z,w))^2+\cdots = \frac{1}{1-zQ(z,w)}\)

を得ます。これに先程の \(Q\) の値を代入すると

\(P(z,w)=\frac{1-2z(1+w)(1+2w)g(z(1+2w))}{1-4z(1+w)^2}\)

となります。\(v=z(1+2w)\) とおいて、以上をまとめると

\((P(\partial_w Q)R)(z,w) = \frac{2(1+w)(1-2(1+w)vg(v))(2wg(v)+4zw(1+w)g'(v))}{\{1-4z(1+w)^2\}^2}\)

となります。この \(z^{N-1}w^{K-1}\) の係数が求めたい値です。

\(g(v)\) の具体値を代入すれば、結局 \(\frac{(1-4v)^{\pm 1/2}}{\{1-4z(1+w)^2\}^2}\) および \(\frac{1}{\{1-4z(1+w)^2\}^2}\) のある項 \(z^nw^k\) の係数を定数解求めればよいことが分かります。以下、この計算を \(O(n)\) で行う方法を示します。 他も同様であるため、ここでは \(\frac{(1-4v)^{1/2}}{\{1-4z(1+w)^2\}^2}\) の \(z^nw^k\) の係数を求める方法を示します。

\(1-4z(1+w)^2=(1-4v)-4zw^2\) であることに注意すると

\(\frac{(1-4v)^{1/2}}{\{1-4z(1+w)^2\}^2} = (1-4v)^{-3/2} \cdot \left(1-\frac{4zw^2}{1-4v}\right)^{-2} = \sum_{k \geq 0} 2^{2k}(k+1)z^kw^{2k}(1-4v)^{-(2k+3)/2}\)

となります。\(v=z(1+2w)\) より、\(0 \leq k \leq n\) に対して \((1-4v)^{-(2k+3)/2}\) の \(v^{n-k}\) の係数が求まればよいです。 これについては以下のような公式があります。

• \((1-4v)^{-(2k+1)/2}\) の \(v^n\) の係数は \(\frac{(2n+2k-1)!!}{(2n-1)!!(2k-1)!!}\binom{2n}{n}\) である。
• \((1-4v)^{-k}\) の \(v^n\) の係数は \(\binom{n+k-1}{k-1} 2^{2n}\) である。

よって階乗・二重階乗を前計算しておくことで、係数は \(O(1)\) の計算量で求まります。 よって、各 \(k\) について係数を \(O(1)\) で求めることで、全体として \(O(n)\) の計算量で \(z^nw^k\) の係数が求まります。

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