CF1810G The Maximum Prefix

你需要生成一个长度不超过 $n$ 的数组 $a$，其中每个 $a_{i}$ 的取值为 $1$ 或 $-1$。 你按照如下方式生成该数组： - 首先，你选择一个整数 $k$（$1\le k \le n$），决定数组 $a$ 的长度。 - 然后，对于每个 $i$（$1\le i \le k$），你以概率 $p_{i}$ 令 $a_{i} = 1$，否则以概率 $1 - p_{i}$ 令 $a_{i} = -1$。 数组生成后，你计算 $s_{i} = a_{1} + a_{2} + a_{3}+ \ldots + a_{i}$，特别地，$s_{0} = 0$。然后令 $S = \displaystyle \max_{i=0}^{k}{s_{i}}$，即 $S$ 是数组 $a$ 的最大前缀和。 你会得到 $n+1$ 个整数 $h_{0}, h_{1}, \ldots, h_{n}$。对于最大前缀和为 $S$ 的数组 $a$，其得分为 $h_{S}$。现在，对于每个 $k$，你需要求出长度为 $k$ 的数组的期望得分，对 $10^9+7$ 取模。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 5000$）——表示测试用例的数量。每组测试用例描述如下。 第一行包含一个整数 $n$（$1\le n \le 5000$）。 接下来的 $n$ 行，每行包含两个整数 $x_{i}$ 和 $y_{i}$（$0 \le x_{i} < 10^9 + 7$，$1\le y_{i} < 10^9 + 7$，$x_{i} \le y_{i}$），表示 $p_{i} = \frac{x_{i}}{y_{i}}$。 下一行包含 $n+1$ 个整数 $h_{0},h_{1}, \ldots, h_{n}$（$0 \le h_{i} < 10^9 + 7$）。 保证所有测试用例中 $n$ 的总和不超过 $5000$。

对于每个测试用例，输出 $n$ 个整数，表示长度为 $1$ 到 $n$ 的数组的期望得分，对 $10^9+7$ 取模。 形式化地，设 $M = 10^9 + 7$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。你需要输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

在第一个测试用例中，如果选择 $k=1$，有 $2$ 种等概率的数组：[1] 和 [-1]。它们的 $S$ 分别为 $1$ 和 $0$。所以期望得分为 $\frac{1}{2}h_{0} + \frac{1}{2}h_{1} = \frac{3}{2}$。如果选择 $k=2$，有 $4$ 种等概率的数组：[1,1]、[1,-1]、[-1,1]、[-1,-1]，它们的 $S$ 分别为 $2,1,0,0$。所以期望得分为 $\frac{1}{2}h_{0} + \frac{1}{4}h_{1} + \frac{1}{4}h_{2} = \frac{7}{4}$。 在第二个测试用例中，无论 $S$ 的值是多少，得分始终为 $1$，所以期望得分始终为 $1$。 由 ChatGPT 4.1 翻译