这是本文档旧的修订版！
K. Game on a Circle
题目大意：有 $n$ 颗石子排成一个环，从石子 $1$ 开始遍历，每遇到一颗石子，有 $p$ 的概率把它删除。对于石子 $c$，问它第 $1,2,\ldots,n$ 个被删除的概率。
题解：先讲一个等下要用的式子。令 $x=(1-p)^{t}$。那么
$$ \begin{aligned} &\sum_{t=0}^{+\infty}x^{e}\\ =&\sum_{t=0}^{+\infty}\left((1-p)^{e}\right)^{t}\\ =&\frac{1}{1-(1-p)^{e}} \end{aligned} $$
找到一个很妙的做法。考虑容斥，设 $f_{i}$ 表示 $c$ 后面恰有 $i$ 个石子的概率，那么
$$ \begin{aligned} f_{i}=\sum_{|T|\ge i,T\in\{1,2,\ldots,n\}-\{c\}}(-1)^{|T|-i}{|T|\choose i}g_{T} \end{aligned} $$
其中 $g_{T}$ 表示 $T$ 中石子都在 $c$ 之后的概率。
那么我们只需要考虑 $T\cup\{c\}$ 这个集合，甚至只需要关心 $T$ 中有几个在 $[1,c-1]$，有几个在 $[c+1,n]$ 即可。
设有 $i$ 个在 $[1,c-1]$，$j$ 个在 $[c+1,n]$，那么这样的 $T$ 有 ${c-1\choose i}{n-c\choose j}$ 个，合法的概率为（设 $c$ 在第 $t$ 轮删除）：
$$ \begin{aligned} &\sum_{t=0}^{+\infty}\left((1-p)^{t+1}\right)^{i}\left((1-p)^{t}\right)^{j+1}p\\ =&\frac{p(1-p)^{i}}{1-(1-p)^{i+j+1}} \end{aligned} $$
显然可以卷积求出 $g$，然后再卷积求出 $f$ 即可。
