ABC295E浅谈垃圾期望
首先明确一点柿子。
- 加法原理，对于同类的概率 $a_1\cdots a_n$，如果要求所有 $i$ 到 $j$ 的概率，就等于 $\sum_{k=i}^ja_k$。
- 乘法原理，对于一类概率 $a_1\cdots a_n$ $b_1\cdots b_n$，求同时满足 $a_i$ 和 $b_j$ 的概率，就等于 $a_i \times b_j$。
接下来推柿子 。
定义 $\operatorname{P}(X)$ 为满足要求 $X$ 的概率。
$
\begin{align}{ans}
&=\sum_{i=1}^mi\operatorname{P}(a_k=i)\\
&=\sum_{i=1}^m\sum_{j=1}^i\operatorname{P}(a_k=i)\\
&=\sum_{j=1}^m\sum_{i=j}^m\operatorname{P}(a_k=i)\\
&=\sum_{j=1}^m\operatorname{P}(a_k\ge j)\\
\end{align}
$
那么只剩考虑 $\operatorname{P}(a_k\ge j)$ 怎么求。
定义原数组有 $x$ 个数不等于 $0$，$y$ 个小于 $j$，$z$ 个 $0$。
大写的字母是题目给的数据。
那么。
$
\begin{align}{\operatorname{P}(a_k\ge j)}&=\sum_{p=0}^{\min(z,K-y-1)}\text{C}_z^{p}\left(\frac{j-1}{M}\right)^p\left(\frac{M-j+1}{M}\right)^{z-p}
\end{align}
$
这个 $\operatorname{P}(a_k\ge j)$ 预处理一下可以 $\text{O}(N)$，外层枚举是 $\text{O}(M)$，所以是 $\text{O}(NM)$。