Solution -「多校联训」光影交错

(mathcal{Description})

Link.

一个游戏包含若干次卡牌抽取，每次以 (p_l) 的概率得到 (+1)，(p_d) 的概率得到 (-1)，否则得到 (0)，操作后以 (p) 的概率结束游戏，求每次抽取后，满足 (+1) 数量大于 (-1) 数量的抽取轮数的期望值。不取模。

(0<ple1)，(0le p_l,p_d,p_l+p_dle 1)。

(mathcal{Solution})

我请愿为Tiw 太阳神教的教徒。（

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

[mathcal{A} = sum_{l>dge 0,ege 0} inom{l+d+e}{l,d,e} p_l^lp_d^dp_e^e (1-p)^{l+d+e-1}, ]

即枚举一个抽取后（不一定结束）的状态。此后，把 ((1-p)) 的指数分配到其余三个因子上，令

[egin{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)，有

[egin{aligned} mathcal{A} &=frac{1}{1-p} sum_{l>dge0,ege0} inom{l+d+e}{l,d,e}p_e'^ep_d'^dp_l'^l\ &= frac{1}{1-p} sum_{lge dge 0} inom{l+d}{d} p_l'^lp_d'^d sum_{ege 0}inom{l+d+e}{e}p_e'^e. end{aligned} ]

最后的级数形如 (sum_{ige 0}inom{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>dge0} inom{l+d}{d}p_l'^lp_d'^d frac{1}{(1-p_e')^{l+d+1}}. ]

按照先前的套路分配指数，再令

[egin{cases} p_l''=frac{p_l'}{1-p_e'}\ p_d''=frac{p_d'}{1-p_e'} end{cases}, ]

代入整理，得到

[mathcal{A}=frac{1}{(1-p)(1-p_e')} sum_{l>dge0} inom{l+d}{d} p_l''^lp_d''^d. ]

我们固定 (l)，挑出此时 (d) 的和式来研究，记

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

错位相减，左右乘 ((1-p_d''))，对齐求和指标 (d) 以化简，最终得到

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

令 (a_l=inom{2(l-1)}{l-1}p_d''^{l-1}-inom{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}) 的指数：

[egin{aligned} mathcal{A} &= frac{1}{(1-p)(1-p_e')} sum_{lge0} p_l''^l sum_{i=1}^l frac{a_i}{(1-p_d'')^{l-i+1}} \ &= frac{1}{(1-p)(1-p_e')} sum_{ige1} frac{a_i}{(1-p_d'')^{-i+1}} sum_{lge i} left(frac{p_l''}{1-p_d''} ight)^l. end{aligned} ]

注意到最后的级数是等比数列求和，先考虑它的收敛性：

[egin{aligned} 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. end{aligned} ]

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

[egin{aligned} mathcal{A} &= frac{1}{(1-p)(1-p_e')} sum_{ige1}frac{a_i}{(1-p_e'')^{-i+1}}cdot frac{q^i}{1-q} \ &= frac{1}{(1-p)(1-p_e')(1-q)} sum_{ige1} q^i left{ inom{2(i-1)}{i-1}[p_d''(1-p_d'')]^{i-1} - p_d''inom{2i-1}{i-1}[p_d''(1-p_d'')]^{i-1} ight} \ &= frac{q}{(1-p)(1-p_e')(1-q)} sum_{ige1} left[ inom{2(i-1)}{i-1}(p_d''p_l'')^{i-1} - p_d''inom{2i-1}{i-1}(p_d''p_l'')^{i-1} ight]. end{aligned} ]

最后的最后，研究级数 (sum_{ige0}inom{2i}{i}) 和 (sum_{ige0}inom{2i-1}{i})。考虑到 Catalan 数的 GF：

[egin{aligned} C(x) &= sum_{ige0}frac{inom{2i}{i}}{i+1}x^i\ &= frac{1-(1-4x)^{frac{1}{2}}}{2}, end{aligned} ]

利用位移和求导消掉分母，得到 (F(x)=sum_{ige0}inom{2i}{i}x^i) 的封闭形式：

[egin{aligned} lbrack xC(x) brack' &= left[ frac{1-(1-4x)^{frac{1}{2}}}{2} ight]' \ &= (1-4x)^{-frac{1}{2}} \ &= F(x). end{aligned} ]

接着用 (F(x)) 配凑出 (G(x)=sum_{ige0}inom{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 ight] ight} ]

能直接 (mathcal O(1)) 计算啦。顺便检查一下 ((1-4p_d''p_l'')) 能否开根。注意到 (p_d''+p_l''le 1)，所以

[egin{aligned} p_d''p_l''&le frac{(p_l''+p_r'')^2}{4}\ &le frac{1}{4}. end{aligned} ]

能开根，计算即可。注意特判 (p=1) 和 (p_l=0) 的情况（不然会爆 nan qwq）。

(mathcal{Code})

/*~Rainybunny~*/

#include <cmath>
#include <cstdio>
#include <cassert>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

const int N = 1e7;
double pl, pd, pe, p, f[N + 5], g[N + 5];

inline void solve() {
    if ( p == 1 ) return void( printf( "%.12f
", pl ) );
    if ( pl == 0 ) return void( printf( "%.12f
", 0. ) );
    double c = pe * ( 1 - p ), // pe'
      a = ( 1 - p ) * pl / ( 1 - c ), // pl''
      b = ( 1 - p ) * pd / ( 1 - c ), // pd''
      q = a / ( 1 - b ), r = a * b, // pl''/(1-pd''); pl''pd''
      u = 1 / sqrt( 1 - 4 * r );
    printf( "%.12f
", q / ( 1 - p ) / ( 1 - c ) / ( 1 - q )
      * ( !a || !b ? 1 : ( u - b / ( 2 * r ) * ( u - 1 ) ) ) );
}

int main() {
    freopen( "augury.in", "r", stdin );
    freopen( "augury.out", "w", stdout );

    int T;
    scanf( "%*d %d", &T );
    while ( T-- ) {
        scanf( "%lf %lf %lf", &pl, &pd, &p ), pe = 1 - pl - pd;
        solve();
    }
    return 0;
}