P6046 纯粹容器

· · 个人记录

这个题目是真好！

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

E_{t_i}=∑P[i\geq x]

这是阿贝尔代换

我们看 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}} 这个式子

\underline{A} \sum\limits_{x=1}^{n-1}\frac{\dbinom{n-1-i}{x-i}}{\dbinom{n-1}{x}}=\frac{\sum\limits_{x=1}^nx^{\underline{i}}}{(n-1)^{\underline{i}}}

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

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