P6046 纯粹容器

这个题目是真好！

考虑一个点存活的期望为 $t_i$

这是阿贝尔代换

我们看 $P[i\geq x]$。相当于操作 $x$ 轮， $i$ 没有被更大的数合并的概率

对于每个容器，它左边第一个比它大的距离它 $a$ 个（中间有 $a-1$ 个），右边第一个比它大的距离它 $b$ 个（中间有 $b-1$ 个）。这可以用单调栈 $O(n)$ 求出

操作 $x$ 轮，一共有 $x!\dbinom{n-1}{x}$ 种方案，其中可行的方案一共有 $x! \Bigg(\dbinom{n-1}{x}-\dbinom{n-1-a}{m-a}-\dbinom{n-1-b}{m+b}+\dbinom{n-1-a-b}{m-a-b}\Bigg)$ 种（用容斥可推得，生成函数我不会。。。）

那么概率就是 $\frac{x! \Bigg(\dbinom{n-1}{x}-\dbinom{n-1-a}{m-a}-\dbinom{n-1-b}{m+b}+\dbinom{n-1-a-b}{m-a-b}\Bigg)}{x!\dbinom{n-1}{x}}$

然后我们化简 $\sum\limits_{x=1}^{n-1}\frac{\dbinom{n-1-i}{x-i}}{\dbinom{n-1}{x}}$ 这个式子

然后 $\sum\limits_{x=1}^{n-1}x^{\underline{i}}=\frac{n^{\underline{i+1}}}{i+1}$

所以原式 $=\frac{n}{i+1}$