Atcoder ABC 263E 期望,数学()

题意

有\(n\)个地方,编号为\(1\sim n\),每个地方有一个骰子,骰子上标有整数\(0,1,\cdots , A_i\),一个人在\(i\)掷骰子到\(j\),那么他会走到编号为\(i+j\)的地方。若一个人不在编号为\(n\)的地方,那么他会一直投骰子。求投骰子的期望次数。\(n \le 2 \times 10^5,A_i \le n – i\).

Solution

根据套路,设\(dp_i\)为\(i\)到\(n\)的期望次数,有\(dp_n=0\).
考虑\(dp_i(i < n)\)的情况,发现投到0的情况有点难处理,根据期望的线性性,单独处理。

其中\(X\)是投到\(0\)后投骰子的期望步数。
推导\(X\):

前缀和搞搞即可。

(本文参考本题官方Editorial,并对一些个人觉得有点问题的地方进行了修改,如有错误请指出)

————————

题意

有\(n\)个地方,编号为\(1\sim n\),每个地方有一个骰子,骰子上标有整数\(0,1,\cdots , A_i\),一个人在\(i\)掷骰子到\(j\),那么他会走到编号为\(i+j\)的地方。若一个人不在编号为\(n\)的地方,那么他会一直投骰子。求投骰子的期望次数。\(n \le 2 \times 10^5,A_i \le n – i\).

Solution

根据套路,设\(dp_i\)为\(i\)到\(n\)的期望次数,有\(dp_n=0\).
考虑\(dp_i(i < n)\)的情况,发现投到0的情况有点难处理,根据期望的线性性,单独处理。

其中\(X\)是投到\(0\)后投骰子的期望步数。
推导\(X\):

前缀和搞搞即可。

(本文参考本题官方Editorial,并对一些个人觉得有点问题的地方进行了修改,如有错误请指出)