The Maximum Prefix (Codeforces 1810G)
Tags: DP, dp

You're going to generate an array $$$a$$$ with a length of at most $$$n$$$, where each $$$a_{i}$$$ equals either $$$1$$$ or $$$-1$$$.You generate this array in the following way.   First, you choose some integer $$$k$$$ ($$$1\le k \le n$$$), which decides the length of $$$a$$$.  Then, for each $$$i$$$ ($$$1\le i \le k$$$), you set $$$a_{i} = 1$$$ with probability $$$p_{i}$$$, otherwise set $$$a_{i} = -1$$$ (with probability $$$1 - p_{i}$$$). After the array is generated, you calculate $$$s_{i} = a_{1} + a_{2} + a_{3}+ \ldots + a_{i}$$$. Specially, $$$s_{0} = 0$$$. Then you let $$$S$$$ equal to $$$\displaystyle \max_{i=0}^{k}{s_{i}}$$$. That is, $$$S$$$ is the maximum prefix sum of the array $$$a$$$.You are given $$$n+1$$$ integers $$$h_{0} , h_{1}, \ldots ,h_{n}$$$. The score of an array $$$a$$$ with maximum prefix sum $$$S$$$ is $$$h_{S}$$$. Now, for each $$$k$$$, you want to know the expected score for an array of length $$$k$$$ modulo $$$10^9+7$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5000$$$) — the number of test cases. Their description follows.The first line contains an integer $$$n$$$ ($$$1\le n \le 5000$$$).Then for the following $$$n$$$ lines, each line contains two integers $$$x_{i}$$$ and $$$y_{i}$$$ ($$$0 \le x_{i} < 10^9 + 7$$$, $$$1\le y_{i} < 10^9 + 7$$$, $$$x_{i} \le y_{i}$$$), indicating $$$p_{i} = \frac{x_{i}}{y_{i}}$$$.The next line contains $$$n+1$$$ integers $$$h_{0},h_{1}, \ldots, h_{n}$$$ ($$$0 \le h_{i} < 10^9 + 7$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output: For each test case, output $$$n$$$ integers in one single line, the $$$i$$$-th of which denotes the expected score for an array of length $$$i$$$, 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 such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Note: In the first test case, if we choose $$$k=1$$$, there are $$$2$$$ possible arrays with equal probabilities: $$$[1]$$$ and $$$[-1]$$$. The $$$S$$$ values for them are $$$1$$$ and $$$0$$$. So the expected score is $$$\frac{1}{2}h_{0} + \frac{1}{2}h_{1} = \frac{3}{2}$$$. If we choose $$$k=2$$$, there are $$$4$$$ possible arrays with equal probabilities: $$$[1,1]$$$, $$$[1,-1]$$$, $$$[-1,1]$$$, $$$[-1,-1]$$$, and the $$$S$$$ values for them are $$$2,1,0,0$$$. So the expected score is $$$\frac{1}{2}h_{0} + \frac{1}{4}h_{1} + \frac{1}{4}h_{2} = \frac{7}{4}$$$.In the second test case, no matter what the $$$S$$$ value is, the score is always $$$1$$$, so the expected score is always $$$1$$$.

Sample Inputs:
4
2
1 2
1 2
1 2 3
3
1 3
1 4
5 5
1 1 1 1
3
2 5
4 6
0 2
4 3 2 1
5
5 6
5 7
1 6
1 3
4 7
9 0 4 5 2 4

Sample Outputs:
500000005 750000007 
1 1 1 
200000005 333333339 333333339 
500000005 880952391 801587311 781746041 789304620

Solution (Python):
import math
mod = int(1000000000.0 + 7)

def fpow(a, b):
    ans = 1
    while b:
        if b & 1:
            ans = ans * a % mod
        a = a * a % mod
        b >>= 1
    return ans
t = int(input())
for _ in range(t):
    n = int(input())
    p_arr = [0] * n
    q_arr = [0] * n
    for i in range(n):
        (x, y) = map(int, input().split())
        p = x * fpow(y, mod - 2) % mod
        p_arr[i] = p
        q_arr[i] = (1 - p_arr[i] + mod) % mod
    h_arr = list(map(int, input().split()))
    sol = [[0] * (n + 1), [0] * (n + 1)]
    sol[0] = h_arr
    result = [0] * n
    for i in range(1, n + 1):
        sol[1] = [(p_arr[i - 1] * sol[0][j + 1] + q_arr[i - 1] * sol[0][max(0, j - 1)]) % mod for j in range(n)] + [q_arr[i - 1] * sol[0][n] % mod]
        sol[0] = [e for e in sol[1]]
        result[i - 1] = sol[1][0]
    print(*result)

Solution (Python):
mod = int(1000000000.0 + 7)

def binPow(b, e):
    r = 1
    while e:
        if e % 2 == 1:
            r = r * b % mod
        b = b * b % mod
        e = e // 2
    return int(r)

def P(s):
    (x, y) = [v for v in map(int, s.split(' '))]
    return x * binPow(y, mod - 2) % mod

def solve():
    n = int(input())
    p = [P(input()) for i in range(n)]
    h = [x for x in map(int, input().split())]
    dp = [[0] * (n + 4) for i in range(n + 2)]
    for j in range(n + 1):
        dp[0][j] = h[j]
    for i in range(1, n + 1):
        for j in range(n + 1):
            dp[i][j] = (p[i - 1] * dp[i - 1][j + 1] + (1 - p[i - 1]) % mod * dp[i - 1][max(j - 1, 0)]) % mod
    for k in range(1, n + 1):
        print(dp[k][0], end=' ')
    print('')
t = int(input())
for _ in range(t):
    solve()

Solution (Python):
mod = int(1000000000.0 + 7)

def binPow(b, e):
    r = 1
    while e:
        if e % 2 == 1:
            r = r * b % mod
        b = b * b % mod
        e = e // 2
    return int(r)

def P(s):
    (x, y) = [v for v in map(int, s.split(' '))]
    return x * binPow(y, mod - 2) % mod

def Caso():
    n = int(input())
    p = [P(input()) for i in range(n)]
    h = [x for x in map(int, input().split())]
    dp = [[0] * (n + 4) for i in range(n + 2)]
    for j in range(n + 1):
        dp[0][j] = h[j]
    for i in range(1, n + 1):
        for j in range(n + 1):
            dp[i][j] = (p[i - 1] * dp[i - 1][j + 1] + (1 - p[i - 1]) % mod * dp[i - 1][max(j - 1, 0)]) % mod
    for k in range(1, n + 1):
        print(dp[k][0], end=' ')
    print('')
t = int(input())
for _ in range(t):
    Caso()