Tenzing and Random Operations CF1842G 题解

设 \(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}\)。