Tenzing and Random Operations (Codeforces 1842G)
Tags: Math, probabilities

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 \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}$$$.

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$$$.

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$$$.

Sample Inputs:
2 2 5
2 2

5 7 9
9 9 8 2 4

Sample Outputs:
84

975544726

Solution (Python):
MOD = 10 ** 9 + 7
(N, M, V) = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] * (N + 1)
dp[0] = 1
for (i, x) in enumerate(A):
    ndp = [0] * (N + 1)
    for a in range(N + 1):
        ndp[a] = (ndp[a] + dp[a] * (x + a * V % MOD)) % MOD
    p = (i + 1) * pow(N, MOD - 2, MOD) % MOD
    for a in range(N):
        ndp[a + 1] = (ndp[a + 1] + (M - a) * dp[a] % MOD * p % MOD * V % MOD) % MOD
    dp = ndp[:]
print(sum(dp) % MOD)

Solution (Python):
MOD = 10 ** 9 + 7
(N, M, V) = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] * (N + 1)
dp[0] = 1
for (i, x) in enumerate(A):
    ndp = [0] * (N + 1)
    for a in range(N + 1):
        ndp[a] = (ndp[a] + dp[a] * (x + a * V % MOD)) % MOD
    p = (i + 1) * pow(N, MOD - 2, MOD) % MOD
    for a in range(N):
        ndp[a + 1] = (ndp[a + 1] + (M - a) * dp[a] % MOD * p % MOD * V % MOD) % MOD
    dp = ndp[:]
print(sum(dp) % MOD)

Solution (Python):
from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
from bisect import bisect_left as lower_bound, bisect_right as upper_bound

def so():
    return int(input())

def st():
    return input()

def mj():
    return map(int, input().strip().split(' '))

def msj():
    return map(str, input().strip().split(' '))

def le():
    return list(map(int, input().split()))

def rc():
    return map(float, input().split())

def lebe():
    return list(map(str, input().split()))

def dmain():
    sys.setrecursionlimit(1000000)
    threading.stack_size(1024000)
    thread = threading.Thread(target=main)
    thread.start()

def joro(L):
    return ''.join(map(str, L))

def joron(L):
    return '\n'.join(map(str, L))

def decimalToBinary(n):
    return bin(n).replace('0b', '')

def isprime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def npr(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
    while start <= end:
        middle = (end + start) // 2
        if li[middle] >= num:
            answer = middle
            end = middle - 1
        else:
            start = middle + 1
    return answer

def upper_bound(li, num):
    answer = -1
    start = 0
    end = len(li) - 1
    while start <= end:
        middle = (end + start) // 2
        if li[middle] <= num:
            answer = middle
            start = middle + 1
        else:
            end = middle - 1
    return answer

def tir(a, b, c):
    if 0 == c:
        return 1
    if len(a) <= b:
        return 0
    if c != -1:
        return tir(a, 1 + b, c + a[b]) or tir(a, b + 1, c - a[b]) or tir(a, 1 + b, c)
    else:
        return tir(a, 1 + b, a[b]) or tir(a, b + 1, -a[b]) or tir(a, 1 + b, -1)

def abs(x):
    return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
    ans = -1
    while lb <= ub:
        mid = (lb + ub) // 2
        if li[mid] > val:
            ub = mid - 1
        elif val > li[mid]:
            lb = mid + 1
        else:
            ans = mid
            break
    return ans

def kadane(x):
    sum_so_far = 0
    current_sum = 0
    for i in x:
        current_sum += i
        if current_sum < 0:
            current_sum = 0
        else:
            sum_so_far = max(sum_so_far, current_sum)
    return sum_so_far

def pref(li):
    pref_sum = [0]
    for i in li:
        pref_sum.append(pref_sum[-1] + i)
    return pref_sum

def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    li = []
    while p * p <= n:
        if prime[p] == True:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    for p in range(2, len(prime)):
        if prime[p]:
            li.append(p)
    return li

def primefactors(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    for i in range(3, int(sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n //= i
    if n > 2:
        factors.append(n)
    return factors

def read():
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

def tr(n):
    return n * (n + 1) // 2
boi = int(1000000000.0 + 7)
doi = int(1000000000.0 + 7)
hoi = int(600000.0 + 5)
poi = int(5000.0 + 100)
d = []
for i in range(poi):
    Lo = []
    for j in range(poi):
        Lo.append(0)
    d.append(Lo)
L = [0] * poi
y = 'yes'
n = 'no'

def bulli(x):
    return bin(x).count('1')
import sys
f = [0] * hoi
r = [0] * hoi
from heapq import heappush, heappop, heapify

def ty(a, b):
    rr = 1
    while b:
        if b % 2:
            rr = rr * a % boi
        b = b // 2
        a = a * a % boi
    return rr

def inv(a):
    re = 1
    for i in range(1, 1 + a):
        re = re * i % boi
    re = ty(re, boi - 2)
    return re

def ncr(m, k):
    if m < 0 or k < 0 or k > m:
        return 0
    return f[m] * r[k] % boi * r[m - k] % boi

def gosa(a, b):
    if 0 != b:
        return gosa(b, a % b)
    return a

def iu():
    import sys
    import math as my
    import functools
    import bisect as bs
    input = sys.stdin.readline
    from collections import deque, defaultdict
    (a, b, c) = mj()
    d[0][0] = 1
    P = le()
    bec = 0
    for i in range(1, 1 + a):
        L[i] = P[i - 1]
    for i in range(1, 1 + a):
        for j in range(1 + a):
            d[i][1 + j] = d[i - 1][j] * i % boi * (b - j) % boi * c % boi
            d[i][j] = (d[i][j] + d[i - 1][j] * ((L[i] + j * c) % boi)) % boi
    u = min(a, b)
    for i in range(1 + u):
        d[a][i] = d[a][i] * ty(a, b - i) % boi
    for i in range(1 + u):
        bec = (bec + d[a][i]) % boi
    bec = bec * ty(ty(a, b), boi - 2) % boi
    print(bec)

def main():
    """"""
    for i in range(1):
        iu()
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
    """"""
    (sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop('end', '\n'))
    if kwargs.pop('flush', False):
        file.flush()
if sys.version_info[0] < 3:
    (sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
    (sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    main()