CF1842G.Tenzing and Random Operations
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Yet another random problem.
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≤i≤n uniformly at random.
- For all j such that i≤j≤n , set aj:=aj+v .
Tenzing wants to know the expected value of ∏i=1nai after performing the m operations, modulo 109+7 .
Formally, let M=109+7 . It can be shown that the answer can be expressed as an irreducible fraction qp , where p and q are integers and q≡0(modM) . Output the integer equal to p⋅q−1modM . In other words, output the integer x that 0≤x<M and x⋅q≡p(modM) .
输入格式
The first line of input contains three integers n , m and v ( 1≤n≤5000 , 1≤m,v≤109 ).
The second line of input contains n integers a1,a2,…,an ( 1≤ai≤109 ).
输出格式
Output the expected value of ∏i=1nai modulo 109+7 .
输入输出样例
输入#1
2 2 5 2 2
输出#1
84
输入#2
5 7 9 9 9 8 2 4
输出#2
975544726
说明/提示
There are three types of a after performing all the m operations :
1. a1=2,a2=12 with 41 probability.
2. a1=a2=12 with 41 probability.
3. a1=7,a2=12 with 21 probability.
So the expected value of a1⋅a2 is 41⋅(24+144)+21⋅84=84 .