310292: CF1810G. The Maximum Prefix
Description
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$.
InputEach 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$.
OutputFor 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}$.
ExampleInput4 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 4Output
500000005 750000007 1 1 1 200000005 333333339 333333339 500000005 880952391 801587311 781746041 789304620Note
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$.
Input
题意翻译
构造一个长度最多为 $n$ 的数组 $a$，其每个元素均为 $1$ 或 $-1$。生成方式如下： + 选择任意整数 $k\in[1,n]$ 作为 $a$ 的长度。 + 对于 $\forall i\in[1,k]$，有 $p_i$ 的概率设 $a_i=1$，有 $1-p_i$ 的概率设 $a_i=-1$。 在数列被生成后，计算 $s_i=a_1+a_2+a_3+...+a_i$。特别地，$s_0=0$。此时 $s$ 数组的最大前缀和 $S=max_{i=0}^ks_i$。 现在给定 $n+1$ 个正整数 $h_0,h_1,...,h_n$。$a$ 数组最大前缀和 $S$ 的分数为 $h_s$。现在，对于每个 $k$，你要求出一个数组长度为 $k$ 的期望分数对 $10^9+7$ 取模的结果。Output
给定一个整数n（1≤n≤5000），生成一个长度为n的数组a，其中每个元素a[i]等于1或-1。首先，选择一个整数k（1≤k≤n），确定数组a的长度。然后，对于每个i（1≤i≤k），以概率p[i]设置a[i]=1，否则以概率（1-p[i]）设置a[i]=-1。生成数组后，计算s[i]=a[1]+a[2]+...+a[i]。特别地，s[0]=0。然后令S等于max_{i=0}^{k}s[i]，即S是数组a的最大前缀和。给定n+1个整数h[0],h[1],...,h[n]，数组a的得分为h
输入数据格式：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤5000）——测试用例的数量。接下来的描述如下：
- 第一行包含一个整数n（1≤n≤5000）。
- 接下来的n行，每行包含两个整数x[i]和y[i]（0≤x[i]<10^9+7，1≤y[i]<10^9+7，x[i]≤y[i]），表示p[i]=x[i]/y[i]。
- 下一行包含n+1个整数h[0],h[1],...,h[n]（0≤h[i]<10^9+7）。
- 保证所有测试用例的n之和不超过5000。
输出数据格式：
对于每个测试用例，输出n个整数，其中第i个表示长度为i的数组的期望得分，模10^9+7。形式上，设M=10^9+7。答案可以表示为不可约分数p/q，其中p和q是整数，且q≡0(mod M)。输出等于p⋅q^(-1)mod M的整数。换句话说，输出一个整数x，使得0≤x