首先第一眼显然是\(dp\)题
这里提供两种做法
方法1：
设\(dp_i\)表示从\(0 \rightarrow i\)的期望次数，容易得到：
\[\begin{align}
dp_i &= \sum_{j=1}^{+\infty}{(P_i^{j-1} \times (1-P_i) \times (dp_{i-1}+1) \times j)} \\
&= (1-P_i) \times (dp_{i-1}+1) \times \sum_{j=1}^{+\infty}{( P_i^{j-1} \times j )} \\
&= (dp_{i-1}+1) \times \sum_{j=0}^{+\infty}{ P_i^j } \\
&= \frac{dp_{i-1}+1}{1-P_i} \\
&= \frac{dp_{i-1}+1}{1-\frac{x_i}{y_i}} \\
&= \frac{y_i \times (dp_{i-1}+1)}{y_i - x_i} \\
\end{align}
\]
最后只需要写一个快速幂来计算\(inv(y_i - x_i)\)即可，最终复杂度\(O(nlogn)\)，复杂度瓶颈在于快速幂
ps: 这里有一个结论：失败后没有回退的这种期望在该路径上的大小为\(\frac{1}{P}\)，其中\(P\)为成功的概率
方法2：
我们发现正着计算\(j \rightarrow +\infty\)，是不太好处理的。正难则反，我们考虑倒着\(dp\)
不妨设\(dp_i\)表示从\(i \rightarrow n\)的期望步数
容易得到：
\[dp_i = (1 - P_i) \times dp_{i+1} + P_i \times dp_0 + 1
\]
但我们发现这个递推式显然存在一个问题：我们无法计算出\(dp_0\)的值
因此我们考虑用解方程的方法得到\(dp_0\)的值，方法如下：
\[\begin{align}
dp_0 &= (1 - P_1) \times dp_1 + P_1 \times dp_0 + 1 \\
&= (1 - P_1) \times ((1 - P_2) \times dp_2 + P_2 \times dp_0 + 1) + P_1 \times dp_0 + 1 \\
&= (1 - P_1) \times (1 - P_2) \times dp_2 + (1 - P_1) \times P_2 \times dp_0 + (1 - P_1) + P_1 \times dp_0 + 1 \\
&= (1 - P_1) \times (1 - P_2) \times dp_2 + dp_0 \times ((1 - P_1) \times P_2 + P_1) + (1 - P_1) + 1 \\
&= \ ... \\
&= dp_n \times \prod_{i=1}^{n}{(1 - P_i)} + dp_0 \times \sum_{i=1}^{n}{(P_i \times \prod_{j=1}^{i - 1}{(1 - P_j)})} + \sum_{i=1}^{n-1}{(1-P_i)} + 1
\end{align}
\]
其中容易发现\(dp_n = 0\)，且我们不妨设
\[\begin{align}
A &= \sum_{i=1}^{n}{(P_i \times \prod_{j=1}^{i - 1}{(1 - P_j)})} \\
B &= \sum_{i=1}^{n-1}{(1-P_i)} + 1 \\
\end{align}
\]
我们容易求得\(A,B\)的值，我们把他们看成常数，带入原式后容易得到：
\[\begin{align}
dp_0 &= dp_0 \times A + B \\
&= \frac{B}{1 - A}
\end{align}
\]
即为答案，最终复杂度\(O(nlogn)\)，瓶颈仍在快速幂