第一个问题应该对于每次的爬行算出期望上升米数，然后用 $n$ 去除即可（如果不行的话期望dp肯定也是能解决的啦）
感觉后面的问题巨大多难呀，这个应该可以转化成返祖图，然后用 P6835 [Cnoi2020]线形生物 的方法进行期望dp
不会数学的蓝爬了/dk
by 幽云蓝 @ 2021-06-20 12:16:22
失败则下滑一“米”？
by Trinitrotoluene @ 2021-06-20 12:17:07
@[八云蓝](/user/149196) 您这个做法显然不对啊，不能以「每次期望上升距离」来算。例如 $p = \dfrac 12$ 时，期望上升就是 $0$ 了，而这种情况下总能在有限时间内上升到 $n$。
by NaCly_Fish @ 2021-06-20 12:40:15
确实/kk
不过期望dp是显然可做的
by 幽云蓝 @ 2021-06-20 12:53:04
@[NaCly_Fish](/user/115864) 求神鱼给出数学做法/kel
by 幽云蓝 @ 2021-06-20 12:59:18
@[八云蓝](/user/149196) 来的有点晚了，我口胡一个做法，经验证 $p = \dfrac 12$ 的时候是对的（
设 $f_{l,r}$ 为从第 $l$ 格走到第 $r$ 格的期望步数，那么对 $l \in [2,r-1]$ 有关系式：
$$f_{l,r}=1+pf_{l+1,r}+(1-p)f_{l-1,r}$$
将 $r$ 固定为 $n$，就有：
$$(1-p)f_{k-1,n}=f_{k,n}-pf_{k+1,n}-1$$
要计算的答案就是 $f_{1,n}$。
按这个递推关系，可以推出 $f_{k,n} = a_kf_{n-1,n}+b_k \ (k\in[2,r-1])$
然后我们发现还有两个关系式没用到：
$$f_{1,n}=1+f_{2,n}$$
$$f_{2,n}=1+pf_{3,n}+(1-p)f_{1,n}$$
一个简单的线性二元方程组，直接解即可，时空复杂度均为 $\Theta(n)$
by NaCly_Fish @ 2021-06-20 22:59:29
忘了补充一点，因为有 $f_{n-1,n} = 1+(1-p)f_{n-2,n}$，所以上述算法才可行
by NaCly_Fish @ 2021-06-20 23:11:43
@[NaCly_Fish](/user/115864) orz
可惜还是只能 $O(n)$ 的/kk
by 幽云蓝 @ 2021-06-21 18:00:35