Random Kth Max ABC226H

[ABC226H] Random Kth Max

Random Kth Max is the same.

题目链接： [ABC226H] Random Kth Max 。

题目描述：

$n$ 个随机变量，第 $i$ 个随机变量 $X_i$ 服从在 $[L_i,R_i]$ 上连续均匀分布。

求第 $k$ 大的数的期望。

$n\le 50$ ， $0\le L_i<R_i\le 100$ 。

考虑 min-max 容斥，则：

$$\begin{aligned} E[\max_k\{X_1,X_2,\cdots,X_n\}]&=\sum_{T\subseteq\{1,2,\cdots,n\}}(-1)^{|T|+k}\binom{|T|-1}{k-1}E[\min_{i\in T}\{X_i\}]\\ &=\sum_{T\subseteq\{1,2,\cdots,n\}}(-1)^{|T|+k}\binom{|T|-1}{k-1}\int_{a}^{b}\prod_{i\in T}Pr[X_i\ge v]dv \end{aligned}$$

容易发现 $Pr[X_i\ge v]$ 其实是一个分段一次函数，所以我们不妨用 $L_i,R_i$ 划分成几个段，然后分开处理。不妨设当前的段的左右端点为 $a,b$ ，第 $i$ 个随机变量的对应一次函数为 $k_iv+v_i$ ，则：

$$\begin{aligned} E[\max_k\{X_1,X_2,\cdots,X_n\}]&=\sum_{T\subseteq\{1,2,\cdots,n\}}(-1)^{|T|+k}\binom{|T|-1}{k-1}\int_{0}^{\infty}\prod_{i\in T}Pr[X_i\ge v]dv\\ &=\sum_{T\subseteq\{1,2,\cdots,n\}}(-1)^{|T|+k}\binom{|T|-1}{k-1}\int_{0}^{\infty}(\prod_{i\in T}{k_iv+v_i})dv\\ &=\sum_{i=k}^n(-1)^{i+k}\binom{i-1}{k-1}\int_{0}^{\infty}([x^i]\prod_{j=1}^n (1+x(k_jv+v_j)))dv \end{aligned}$$

然后模拟就行。