感觉是比较 educational 的题。
拿到题目应该有一个大致思路，就是考虑最大前缀和的求法，再把它扔到状态里面。
最大前缀和有两种求法：
- 从前往后求，需要维护当前前缀和 \(s\)，当前最大前缀和 \(mx\)，需要记录两个变量，无法承受。
- 从后往前求，只需记录当前最大前缀和 \(mx\)，从 \([i + 1, n]\) 的最大前缀和转移到 \([i, n]\) 的最大前缀和时，我们贪心地判断 \(a_i\) 是否属于最大前缀和，即 \(mx \gets \max(mx + a_i, 0)\)。
于是我们有一个初步的 dp 思路：设 \(f_{i, j}\) 为当前考虑了 \([i, n]\)，其最大前缀和为 \(j\)。有转移：
\[\begin{cases} p_i f_{i + 1, j} \to f_{i, j + 1} \\ (1 - p_i) f_{i + 1, j} \to f_{i, \max(j - 1, 0)} \end{cases}
\]
初值为 \(f_{n + 1, 0} = 1\)，最终 \(ans = \sum\limits_{i = 0}^n h_i f_{1, i}\)。
我们算的只是长度为 \(n\) 的答案，我们希望对于每个长度 \(l\) 都求出答案，但是直接做是 \(O(n^3)\) 的。
注意到我们每次 dp 的转移都是固定的，只是初值不同（长度为 \(l\) 时 dp 初值为 \(f_{l + 1, 0} = 1\)），因此 \(f_{i, j}\) 对答案的贡献也是固定的。我们不妨使用反推贡献系数的 trick，设 \(g_{i, j}\) 为 \(f_{i, j}\) 对 \(ans\) 的贡献系数，那么有转移：
\[g_{i + 1, j} = p_i g_{i, j + 1} + (1 - p_i) g_{i, \max(j - 1, 0)}
\]
初值为 \(g_{1, i} = h_i\)。最终长度为 \(l\) 的答案为 \(g_{l + 1, 0}\)。
时间复杂度降至 \(O(n^2)\)。
code
// Problem: G. The Maximum Prefix
// Contest: Codeforces - CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
// URL: https://codeforces.com/problemset/problem/1810/G
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 5050;
const ll mod = 1000000007;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, p[maxn], f[maxn][maxn], a[maxn];
void solve() {
scanf("%lld", &n);
for (int i = 1, x, y; i <= n; ++i) {
scanf("%d%d", &x, &y);
p[i] = 1LL * x * qpow(y, mod - 2) % mod;
}
for (int i = 0; i <= n; ++i) {
scanf("%lld", &a[i]);
f[1][i] = a[i];
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= n; ++j) {
f[i + 1][j] = ((j < n ? f[i][j + 1] : 0) * p[i] % mod + f[i][max(j - 1, 0)] * (mod + 1 - p[i]) % mod) % mod;
}
}
for (int i = 2; i <= n + 1; ++i) {
printf("%lld ", f[i][0]);
}
putchar('\n');
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}