Tenzing and Random Operations CF1842G 题解-526互联

设 $m$ 次选的位置分别为 $b_{1\sim m}$。

于是答案为 $\mathbb E(\prod\limits_{i = 1}^{n}(a_i + \sum\limits_{j = 1}^{m}[b_j \le i]\cdot v)) = \frac{S}{n^m}$。

首先考虑期望很难做，希望将期望转化为概率形式，发现这样有点困难。

再考虑因为所有方案等概率，将求期望转化为求所有情况下所期望答案的总和，最后除以总方案数即可，即求 $S$。

$S = \sum\limits_{b}\prod\limits_{i = 1}^{n}(a_i + \sum\limits_{j = 1}^{m}[b_j \le i]\cdot v)$，发现最终的 $a_i = a_i + v +\cdots$。

因为答案最终是多个 $n$ 个数相乘得到的数相加，于是答案可以 DP 求出。

具体而言，令 $f_{i,j}$ 代表前 $i$ 个数确定，有 $j$ 个 $b_p$ 已经确定。（注意，对 $v$ 的个数并没有限制）。

对当前这一位分类讨论：

若这一位取 $a_i$，则 $f_{i - 1,j}\cdot a_i\to f_{i,j}$。

若这一位取 $v$（已确定位置的 $b$ 提供），则 $f_{i - 1,j}\cdot v\cdot j\to f_{i,j}$。

若这一位取 $v$（新确定一个 $b$），则 $f_{i - 1,j - 1}\cdot v\cdot (m - j)\cdot i\to f_{i,j} $。

那么初始有 $f_{0,0} = 1$。

最后统计答案 $S = \sum\limits_{i=0}^{\min(n,m)} f_{n,i}\cdot n^{m-i}$。