310496: CF1842G. Tenzing and Random Operations
Description
Tenzing has an array $a$ of length $n$ and an integer $v$.
Tenzing will perform the following operation $m$ times:
- Choose an integer $i$ such that $1 \leq i \leq n$ uniformly at random.
- For all $j$ such that $i \leq j \leq n$, set $a_j := a_j + v$.
Tenzing wants to know the expected value of $\prod_{i=1}^n a_i$ after performing the $m$ operations, modulo $10^9+7$.
Formally, let $M = 10^9+7$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output the integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.
InputThe first line of input contains three integers $n$, $m$ and $v$ ($1\leq n\leq 5000$, $1\leq m,v\leq 10^9$).
The second line of input contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i\leq 10^9$).
OutputOutput the expected value of $\prod_{i=1}^n a_i$ modulo $10^9+7$.
ExamplesInput2 2 5 2 2Output
84Input
5 7 9 9 9 8 2 4Output
975544726Note
There are three types of $a$ after performing all the $m$ operations :
1. $a_1=2,a_2=12$ with $\frac{1}{4}$ probability.
2. $a_1=a_2=12$ with $\frac{1}{4}$ probability.
3. $a_1=7,a_2=12$ with $\frac{1}{2}$ probability.
So the expected value of $a_1\cdot a_2$ is $\frac{1}{4}\cdot (24+144) + \frac{1}{2}\cdot 84=84$.
Input
题意翻译
有一长度为 $n$ 的序列 $a$ 和一整数 $v$，对该序列进行 $m$ 次操作。 每次操作中，等概率地随机选择一整数 $i \in [1, n]$，对所有的 $j \in [i, n]$，赋值 $a_j \gets a_j+v$，求出 $m$ 次操作后 $\Pi_{i=1}^n a_i$ 的期望值，对 $10^9+7$ 取模。 数据范围：$0\leq n \leq 5000$，$1 \leq m, v \leq10^9$，$a_i \in [1, 10^9] \cap \mathbb{Z}$。Output
Tenzing有一个长度为n的数组a和一个整数v。Tenzing将执行以下操作m次：
1. 随机选择一个整数i，使得1≤i≤n。
2. 对于所有j，使得i≤j≤n，设置a_j:=a_j+v。
Tenzing想知道执行m次操作后prod_{i=1}^n a_i的期望值，模10^9+7。
输入输出数据格式：
输入：
第一行包含三个整数n、m和v（1≤n≤5000，1≤m,v≤10^9）。
第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）。
输出：
输出prod_{i=1}^n a_i的期望值模10^9+7。题目大意： Tenzing有一个长度为n的数组a和一个整数v。Tenzing将执行以下操作m次： 1. 随机选择一个整数i，使得1≤i≤n。 2. 对于所有j，使得i≤j≤n，设置a_j:=a_j+v。 Tenzing想知道执行m次操作后prod_{i=1}^n a_i的期望值，模10^9+7。 输入输出数据格式： 输入： 第一行包含三个整数n、m和v（1≤n≤5000，1≤m,v≤10^9）。 第二行包含n个整数a_1,a_2,…,a_n（1≤a_i≤10^9）。 输出： 输出prod_{i=1}^n a_i的期望值模10^9+7。