暑训5-L

题意

有 $n+1$ 个格子，起点位于 $0$ 号格子，终点是 $n$ 号格子；你有若干硬币，对于非终点的格子，每走一步，有 $p$ 的概率成功走到下一个格子，否则尝试消耗 $1$ 个硬币留在原地，若无硬币则回到起点。求对于每个初始硬币数 $m$ ,你从起点走到终点所需的期望步数。

如果你对公式感到困惑可以看看转移图：

alt

这里的方向是实际模拟时状态改变的方向，但推期望的时候是反过来推的。

我们设 $E_{i,j}$ 为剩余 $i$ 个硬币，在第 $j$ 个格子时步数的期望。

对于第 $0$ 层我们有：

E_{0,n}=E_{1,n}=...=0\\ E_{0,i}=pE_{0,i+1}+(1-p)E_{0,0}+1\\

暴力消元可以解出 $E_{0,0}$ ，然后暴力回代得：

E_{0,i}=\frac{1-p^{n-i}}{1-p}((1-p)E_{0,0}+1)=\frac{1-p^{n-i}}{(1-p)p^n}\tag{B}

对于其他层有：

E_{m,i}=pE_{m,i+1}+(1-p)E_{m-1,i}+1\tag{R}

又设差分：

\Delta_{m,i}:=E_{m,i}-E_{m-1,i}\qquad(m\ge 1)

对 $(\text{R})$ 作差分可得：

\Delta_{m,i}=p\,\Delta_{m,i+1}+(1-p)\,\Delta_{m-1,i}, \qquad \Delta_{m,n}=0.\tag{A}

计算 $E_{1,i}\,,\,\Delta_{1,i}$ :

E_{1,i}=p\,E_{1,i+1}+(1-p)\,E_{0,i}+1\\ E_{1,n-k}=(1+\frac{1}{p^n})(\frac{1-p^k}{1-p})-kp^{k-n}=E_{0,n-k}+\frac{1-p^k}{1-p}-kp^{k-n}\\ E_{1,k}=E_{0,k} + \frac{1-p^{n-k}}{1-p}-(n-k)p^{-k}\\ \Delta_{1,i}=\frac{1-p^{n-i}}{1-p}-\frac{n-i}{p^i}\\

考虑 $\Delta_{1,i}$ 对 $\Delta_{m,0}$ 的总贡献：不妨想象一个二维游走，但是这里的递推是定向的，也就是说 $\Delta_{1,i}$ 到 $\Delta_{m,0}$ 的路径数量是确定的。每条路径上的权也是确定的。

第一步一定是 $m+1$ （向右），然后是 $i$ 个 $i-1$ （向上）和 $r=m-2$ 个向右。

\Delta_{m,0}=\sum_{i=0}^{n-1}{\Delta_{1,i}\begin{pmatrix}{r+i}\\i\end{pmatrix}}(1-p)^{m-1}p^i,\qquad(m>1)\tag{C}

化简一下：

\Delta_{m,0}=(1-p)^{m-1}\sum_{i=0}^{n-1}{\begin{pmatrix}{r+i}\\i\end{pmatrix}(\frac{p^i-p^{n}}{1-p}-(n-i))},\qquad(m>1)\tag{C1} \\=(1-p)^{m-1}\left( (\frac{-p^{n}}{1-p}-n)\sum_{i=0}^{n-1}{\begin{pmatrix}{r+i}\\i\end{pmatrix}}+ \sum_{i=0}^{n-1}{i\begin{pmatrix}{r+i}\\i\end{pmatrix}}+ (\frac{1}{1-p})\sum_{i=0}^{n-1}{p^i\begin{pmatrix}{r+i}\\i\end{pmatrix}} \right)

超级拆解.png

我们要 $O(m)$ 算出所有：

A_m=\sum_{i=0}^{n-1}i{\begin{pmatrix}{r+i}\\i\end{pmatrix}}, \qquad B_m=\sum_{i=0}^{n-1}p^i{\begin{pmatrix}{r+i}\\i\end{pmatrix}}, \qquad C_m=\sum_{i=0}^{n-1}{\begin{pmatrix}{r+i}\\i\end{pmatrix}}.

众所周知

C_m=\sum_{i=0}^{n-1}\binom{r+i}{\,i}=\binom{r+n}{\,n-1} \tag{1}

利用

i\,\displaystyle\binom{r+i}{\,i}= (r+i) \displaystyle\binom{r+i-1}{\,i-1}

把求和指标换成 $j=i-1$ 得

\begin{aligned} A_m &=\sum_{j=0}^{n-2}(r+j+1)\binom{r+j}{\,j}\\ &=(r+1)\sum_{j=0}^{n-2}\binom{r+j}{\,j} +\sum_{j=0}^{n-2}j\binom{r+j}{\,j}. \end{aligned}

后一项正是 $A_m$ 自身截去最后一项，于是

A_m=(r+1) \Bigl[\sum_{j=0}^{n-2}\binom{r+j}{\,j}\Bigr] =(m-1)\binom{r+n}{\,n-2}=\frac{(n-1)(m-1)}{m}C_m. \tag{2}

根据加法公式

\binom{r+1+i}{\,i}=\binom{r+i}{\,i}+\binom{r+i}{\,i-1}.

把它对所有 $i<n$ 加权求和可得

B_{m+1}=B_{m}+p\,B_{m+1}-p^{n}C_m,

即

B_{m+1} =\bigl(B_{m}-p^{\,n}C_m\bigr)\,(1-p)^{-1}. \tag{3}

$O(1)$ 更新 $C_m$

C_{m+1}=\binom{m+n-1}{\,n-1} =C_m\;\frac{m+n-1}{m}\quad(m\ge 2). \tag{4}

初值

B_2=\sum_{i=0}^{n-1}p^{\,i} =\frac{1-p^{\,n}}{1-p},\qquad C_2=\binom{n}{\,n-1}=n .

超级拼装.png

\Delta_{m,0}=(1-p)^{m-1} \Bigl[\, \frac{B_m-p^{n}C_m}{1-p} -\bigl(nC_m-A_m\bigr) \Bigr],\qquad m\ge 2. \tag{5}

工程已毕，所有量都已能 $O(1)$ 从上一层更新：