「刚才 abc E 的一个不知道错哪的正推思路」

刚才 abc E 的一个不知道错哪的正推思路

被骇客银狼阻止的越权访问保存失败

刚才 abc E 的一个不知道错哪的正推思路

Missa楼主2022/8/6 21:51

设 $dp_i$ 表示从 $1$ 出发，到 $i$ 就停下的期望步数。

设站在 $i$ ，走到 $j$ 的概率是 $t_{i,j}$ ，站在 $i$ 走出 $i$ 期望 $\dfrac{a_i+1}{a_i}$ 步，所以又设 $f_i=dp_i+\dfrac{a_i+1}{a_i}$ 。于是写出递推式：

dp_i = \dfrac{\sum \limits_{j=1}^{i-1} (t_{i,j} \cdot f_j)}{\sum \limits_{j=1}^{i-1} t_{i,j}}

这样无论是笔算还是写出程序都是 $\frac{487}{105}$ ，求解释，这个递推是哪一步有问题？

2022/8/6 21:51