有一个长为 \(n\) 的环，一个指针从 \(1\) 开始移动，每次指针所在位置有 \(p\) 的概率消失掉， 然后指针向右移动。求每个点是最后消失的概率。

\(n\leqslant 2\times10^5\)

考虑一个点消失后并不将其从环上移除，只是下次其被消失时不操作，这样和原问题是等价的。

为方便推导，设 \(q=1-p\)。设 \(f_n\) 为环长为 \(n\) 时，\(1\) 号点最后消失的概率，得：

\[\large\begin{aligned} f_n&=\sum_{i=0}^\infty pq^i(1-q^i)^{n-1}\\ &=p\sum_{i=0}^\infty q^i\sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^jq^{ij}\\ &=p\sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^j\sum_{i=0}^\infty q^{i(j+1)}\\ &=p\sum_{j=0}^{n-1}\binom{n-1}{j}(-1)^j\frac{1}{1-q^{j+1}}\\ \end{aligned} \]

卷积计算即可。得 \(k\) 号点最后消失的概率为：

\[\large \sum_{i=0}^{k-1}\binom{k-1}{i}p^iq^{k-1-i}f_{n-i} \]

同样卷积计算即可。