CF1842G Tenzing and Random Operations

又一道随机问题。 Tenzing 有一个长度为 $n$ 的数组 $a$ 和一个整数 $v$。 Tenzing 将进行 $m$ 次如下操作： 1. 每次等概率随机选择一个整数 $i$，满足 $1 \leq i \leq n$。 2. 对所有满足 $i \leq j \leq n$ 的 $j$，将 $a_j$ 赋值为 $a_j + v$。 Tenzing 想知道，经过 $m$ 次操作后，$\prod_{i=1}^n a_i$ 的期望值是多少，结果对 $10^9+7$ 取模。 形式化地，设 $M = 10^9+7$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。请输出等于 $p \cdot q^{-1} \bmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

输入的第一行包含三个整数 $n$、$m$ 和 $v$（$1\leq n\leq 5000$，$1\leq m,v\leq 10^9$）。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\leq a_i\leq 10^9$）。

输出 $\prod_{i=1}^n a_i$ 的期望值对 $10^9+7$ 取模的结果。

经过所有 $m$ 次操作后，数组 $a$ 有三种可能的情况： 1. $a_1=2,a_2=12$，概率为 $\frac{1}{4}$。 2. $a_1=a_2=12$，概率为 $\frac{1}{4}$。 3. $a_1=7,a_2=12$，概率为 $\frac{1}{2}$。 因此，$a_1\cdot a_2$ 的期望值为 $\frac{1}{4}\cdot (24+144) + \frac{1}{2}\cdot 84=84$。 由 ChatGPT 4.1 翻译