P6046 纯粹容器
原题
期望不要光往\(dp\)想!!!
期望不要光往\(dp\)想!!!
期望不要光往\(dp\)想!!!
对于每一个数\(a_i\)分别考虑，\(E(t_i)\)表示\(i\)的期望删除轮数；\(P(t_i = x)\)表示\(i\)恰好在第\(i\)轮删除的概率，容易得到：
\[E(t_i) = \sum_{x \geq 1}{x \times P(t_i = x)}
\]
容易发现可能使\(i\)被删除的只有前面距离最近的\(a_x > a_i\)的位置和后面距离最近的\(a_x > a_i\)的位置，我们设这两个位置下标分别为\(pre\)和\(suf\)
我们可以\(O(n)\)暴力计算\(P(t_i = x)\)的值：
\[P(t_i = x) = \frac{x! \times (\sum_{j+k=x-(i-pre),j < suf-i}{\binom{i-pre}{i-pre-1} \binom{suf-i}{j} \binom{n-1-(suf-pre)}{k}}+
\sum_{j+k=x-(suf-i),j < i-pre}{\binom{i-pre}{j} \binom{suf-i}{suf-i-1} \binom{n-1-(suf-pre)}{k}})}{x! \times \binom{n-1}{x}}
\]
这个做法复杂度是\(O(n^3)\)的
我们明显可以感到这个式子不太对劲对吧，感性来说，因为有\(t_i=x\)的限制，我们必须保证第\(x\)轮\(i\)必须被删掉，这个限制似乎成了一种累赘，拉大了计算\(P(t_i=x)\)的复杂度
我们这时候要用一个比较经典的转化：
\[\begin{align}
E(t_i) &= \sum_{x \geq 1}{x \times P(t_i = x)} \\
&= \sum_{x \geq 1}{P(t_i \geq x)}
\end{align}
\]
其中\(P(t_i \geq x)\)表示\(i\)消失的轮数\(\geq x\)的概率
这时候虽然计算\(P\)的复杂度还是不太对，但我们感觉起来就比较舒服了：
\[P(t_i \geq x) = \frac{x! \times \sum_{a+b+c=x, a < (i-pre), b < (suf-i)}{\binom{i-pre}{a} \binom{suf-i}{b} \binom{n-1-(suf-pre)}{c}}}{x! \times \binom{n-1}{x}}
\]
这个做法复杂度是\(O(n^4)\)
虽然式子变得优美了，但这个复杂度不是我们想要的，因此我们考虑怎么优化复杂度
正难则反，我们考虑能不能计算\(P(t_i < x)\)的概率，则\(P(t_i \geq x) = 1 - P(t_i < x)\)
记\(P(A)\)为\(pre∼i\)这一段全部被选的概率，\(P(B)\)表示\(i∼suf\)这一段全部被选的概率;\(P(AB)\)表示\(pre∼suf\)这一段全部被选的概率
我们发现这个比较好做，因为\(t_i < x\)说明\(pre∼i\)和\(i∼suf\)中有一个选了，这个可以用容斥原理解决；
\[\begin{align}
P(t_i < x) &= P(A) + P(B) - P(A+B) \\
&= \frac{\binom{n-1-(i-pre)}{x-(i-pre)}}{\binom{n-1}{x}} + \frac{\binom{n-1-(suf-i)}{x-(suf-i)}}{\binom{n-1}{x}} - \frac{\binom{n-1-(suf-pre)}{x-(suf-pre)}}{\binom{n-1}{x}} \\
&= \frac{\binom{n-1-(i-pre)}{x-(i-pre)}+\binom{n-1-(suf-i)}{x-(suf-i)}-\binom{n-1-(suf-pre)}{x-(suf-pre)}}{\binom{n-1}{x}}
\end{align}
\]
复杂度\(O(n^2)\)
貌似还有\(O(n)\)做法