CF1810G The Maximum Prefix

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

N/A

N/A

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