Solution -「多校聯訓」光影交錯

\(\mathcal{Description}\)

  Link.

  一個遊戲包含若幹次卡牌抽取，每次以 \(p_l\) 的機率得到 \(+1\)，\(p_d\) 的機率得到 \(-1\)，否則得到 \(0\)，操作後以 \(p\) 的機率結束遊戲，求每次抽取後，滿足 \(+1\) 數量大于 \(-1\) 數量的抽取輪數的期望值。不取模。

  \(0<p\le1\)，\(0\le p_l,p_d,p_l+p_d\le 1\)。

\(\mathcal{Solution}\)

  我請願為Tiw 太陽神教的教徒。（

  令 \(p_e=1-p_l-p_r\)，表示得到 \(0\) 的機率。我們直接從答案 \(\mathcal A\) 入手：

\[\mathcal{A} = \sum_{l>d\ge 0,e\ge 0} \binom{l+d+e}{l,d,e} p_l^lp_d^dp_e^e (1-p)^{l+d+e-1},

\]

即枚舉一個抽取後（不一定結束）的狀态。此後，把 \((1-p)\) 的指數配置設定到其餘三個因子上，令

\[\begin{cases}

p_e'=p_e(1-p)\\

p_l'=p_l(1-p)\\

p_d'=p_d(1-p)

\end{cases},

帶入 \(\mathcal{A}\)，同時發現 \(e\) 的限制較少，是以單獨枚舉 \(e\)，有

\[\begin{aligned}

\mathcal{A} &=\frac{1}{1-p} \sum_{l>d\ge0,e\ge0} \binom{l+d+e}{l,d,e}p_e'^ep_d'^dp_l'^l\\

&= \frac{1}{1-p} \sum_{l\ge d\ge 0} \binom{l+d}{d} p_l'^lp_d'^d \sum_{e\ge 0}\binom{l+d+e}{e}p_e'^e.

\end{aligned}

  最後的級數形如 \(\sum_{i\ge 0}\binom{i+t}{i}x^i=\frac{1}{(1-x)^t}\)，當 \(p_e=1\) 時認為 \(\frac{1}{0^0}=1\)，即任意 \(p_e\) 在這個 GF 的收斂域中，可以直接帶入。是以

\[\mathcal{A} = \frac{1}{1-p} \sum_{l>d\ge0} \binom{l+d}{d}p_l'^lp_d'^d \frac{1}{(1-p_e')^{l+d+1}}.

  按照先前的套路配置設定指數，再令

p_l''=\frac{p_l'}{1-p_e'}\\

p_d''=\frac{p_d'}{1-p_e'}

代入整理，得到

\[\mathcal{A}=\frac{1}{(1-p)(1-p_e')} \sum_{l>d\ge0} \binom{l+d}{d} p_l''^lp_d''^d.

  我們固定 \(l\)，挑出此時 \(d\) 的和式來研究，記

\[S_d(l)=\sum_{0\le d<l}\binom{l+d}{d}p_d''^d.

錯位相減，左右乘 \((1-p_d'')\)，對齊求和名額 \(d\) 以化簡，最終得到

\[(1-p_d'')S_d(l)=S_d(l-1)+\binom{2(l-1)}{l-1}p_d''^{l-1}-\binom{2l-1}{l-1}p_d''^l.

令 \(a_l=\binom{2(l-1)}{l-1}p_d''^{l-1}-\binom{2l-1}{l-1}p_d''^l\)，自然得到

\[S_d(l) = \sum_{i=0}^l \frac{a_i}{(1-p_d'')^{l-i+1}}.

  代回 \(\mathcal{A}\)，交換求和名額并配置設定 \((1-p_d'')^{l-i+1}\) 的指數：

\mathcal{A} &= \frac{1}{(1-p)(1-p_e')} \sum_{l\ge0} p_l''^l \sum_{i=1}^l \frac{a_i}{(1-p_d'')^{l-i+1}} \\

&= \frac{1}{(1-p)(1-p_e')} \sum_{i\ge1} \frac{a_i}{(1-p_d'')^{-i+1}} \sum_{l\ge i} \left(\frac{p_l''}{1-p_d''}\right)^l.

注意到最後的級數是等比數列求和，先考慮它的收斂性：

1-p_d''-p_l'' &= 1-\frac{(1-p)p_d+(1-p)p_l}{1-(1-p)p_e} \\

&= \frac{1-(1-p)p_e-(1-p)p_d-(1-p)p_l}{1-(1-p)p_e} \\

&= \frac{p}{1-(1-p)p_e} \\

&>0.

收斂啦。不妨令 \(q=\frac{p_l''}{1-p_d''}\)，整理式子：

\mathcal{A} &= \frac{1}{(1-p)(1-p_e')} \sum_{i\ge1}\frac{a_i}{(1-p_e'')^{-i+1}}\cdot \frac{q^i}{1-q} \\

&= \frac{1}{(1-p)(1-p_e')(1-q)} \sum_{i\ge1} q^i \left\{ \binom{2(i-1)}{i-1}[p_d''(1-p_d'')]^{i-1} - p_d''\binom{2i-1}{i-1}[p_d''(1-p_d'')]^{i-1} \right\} \\

&= \frac{q}{(1-p)(1-p_e')(1-q)} \sum_{i\ge1} \left[ \binom{2(i-1)}{i-1}(p_d''p_l'')^{i-1} - p_d''\binom{2i-1}{i-1}(p_d''p_l'')^{i-1} \right].

  最後的最後，研究級數 \(\sum_{i\ge0}\binom{2i}{i}\) 和 \(\sum_{i\ge0}\binom{2i-1}{i}\)。考慮到 Catalan 數的 GF：

C(x) &= \sum_{i\ge0}\frac{\binom{2i}{i}}{i+1}x^i\\

&= \frac{1-(1-4x)^{\frac{1}{2}}}{2},

利用位移和求導消掉分母，得到 \(F(x)=\sum_{i\ge0}\binom{2i}{i}x^i\) 的封閉形式：

\lbrack xC(x)\rbrack' &= \left[ \frac{1-(1-4x)^{\frac{1}{2}}}{2} \right]' \\

&= (1-4x)^{-\frac{1}{2}} \\

&= F(x).

接着用 \(F(x)\) 配湊出 \(G(x)=\sum_{i\ge0}\binom{2i}{i+1}x^i\)，結果是

\[G(x)=\frac{1-(1-4x)^{\frac{1}{2}}}{2x}.

  将結果代入 \(\mathcal{A}\)：

\[\mathcal{A} = \frac{q}{(1-p)(1-p_e')(1-q)}\left\{ (1-4p_d''p_l'')^{-\frac{1}{2}} - \frac{1}{2p_l''}\left[ (1-4p_d''p_l'')^{-\frac{1}{2}}-1 \right] \right\}

能直接 \(\mathcal O(1)\) 計算啦。順便檢查一下 \((1-4p_d''p_l'')\) 能否開根。注意到 \(p_d''+p_l''\le 1\)，是以

p_d''p_l''&\le \frac{(p_l''+p_r'')^2}{4}\\

&\le \frac{1}{4}.

能開根，計算即可。注意特判 \(p=1\) 和 \(p_l=0\) 的情況（不然會爆 <code>nan</code> qwq）。