Tenzing and Random Operations
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
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}$.
The 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$).
Output the expected value of $\prod_{i=1}^n a_i$ modulo $10^9+7$.
Input
The 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$).
Output
Output the expected value of $\prod_{i=1}^n a_i$ modulo $10^9+7$.
2 2 5
2 2
5 7 9
9 9 8 2 4
84
975544726
Note
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$.
20240118期望的线性选讲
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 12
- Start at
- 2024-1-18 8:00
- End at
- 2024-1-23 8:00
- Duration
- 120 hour(s)
- Host
-
梁泽贤 (liangzexian)
- Partic.
- 19