CF1810G.The Maximum Prefix
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You're going to generate an array a with a length of at most n , where each ai equals either 1 or −1 .
You generate this array in the following way.
- First, you choose some integer k ( 1≤k≤n ), which decides the length of a .
- Then, for each i ( 1≤i≤k ), you set ai=1 with probability pi , otherwise set ai=−1 (with probability 1−pi ).
After the array is generated, you calculate si=a1+a2+a3+…+ai . Specially, s0=0 . Then you let S equal to i=0maxksi . That is, S is the maximum prefix sum of the array a .
You are given n+1 integers h0,h1,…,hn . The score of an array a with maximum prefix sum S is hS . Now, for each k , you want to know the expected score for an array of length k modulo 109+7 .
输入格式
Each test contains multiple test cases. The first line contains a single integer t ( 1≤t≤5000 ) — the number of test cases. Their description follows.
The first line contains an integer n ( 1≤n≤5000 ).
Then for the following n lines, each line contains two integers xi and yi ( 0≤xi<109+7 , 1≤yi<109+7 , xi≤yi ), indicating pi=yixi .
The next line contains n+1 integers h0,h1,…,hn ( 0≤hi<109+7 ).
It is guaranteed that the sum of n over all test cases does not exceed 5000 .
输出格式
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 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 such an integer x that 0≤x<M and x⋅q≡p(modM) .
输入输出样例
输入#1
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
输出#1
500000005 750000007 1 1 1 200000005 333333339 333333339 500000005 880952391 801587311 781746041 789304620
说明/提示
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 21h0+21h1=23 . 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 21h0+41h1+41h2=47 .
In the second test case, no matter what the S value is, the score is always 1 , so the expected score is always 1 .