挺小清新的一道计数题。
首先先分析下这个“最大前缀和”，按照最朴素的思路就是扫一遍每个前缀，然后记录一下当前的 \(sum\) 与前面的 \(mx\)，但是如果你一直陷在这个思路上你就似了，因为按照这个思路做，你 DP 状态里需要记录 \(sum\) 和 \(mx\) 两个维度，算上下标一维总共是 \(n^3\)，并且没有任何办法省掉当中任何一个循环，所以哪怕解决 \(k=n\) 的问题都至少需要 \(O(n^3)\)。
考虑换一个角度处理这个“最大前缀和”，我们倒着 DP，\(f_i\) 表示 \([i,n]\) 后缀的最大前缀和，显然 \(f_i=\max(f_{i+1}+a_i,0)\)。这样的好处一目了然：我们倒着 DP 的时候，只用记录一个维度也就是当前位置的 \(f_i\)，于是 \(k=n\) 的情况就迎刃而解了：\(dp_{i,j}\) 表示考虑到 \(i\)，目前 \(f_i=j\) 的概率。
但是还有一个问题，就是我们对 \(k=1,2,3,\cdots,n\) 求答案，相当于每次在末尾加一个数，这就导致我们 DP 状态不得不重新计算，而每次重新计算复杂度又变成了三方。这个 bug 的修补方法也比较 trivial，倒着 DP 行不通，我们就再改回正着 DP 呗。我们将 DP 状态改为：设 \(dp_{i,j}\) 表示当前在 \(i\)，在已知 \(f_{i+1}=j\) 的情况，随机填 \([1,i]\) 的前缀，得分的期望值。考虑这样的转移：
- 如果 \(j\ne 0\)：
- \(dp_{i,j}·a_{i+1}\to dp_{i+1,j-1}\)
- \(dp_{i,j}·(1-a_{i+1})\to dp_{i+1,j+1}\)
- 如果 \(j=0\)：
- \(dp_{i,j}·(1-a_{i+1})\to dp_{i+1,0}\)
- \(dp_{i,j}·(1-a_{i+1})\to dp_{i+1,1}\)
初值 \(dp_{0,i}=h_i\)，最终所求即为 \(dp_{i,0}\)。
代码非常短：
const int MAXN=5000;
const int MOD=1e9+7;
int qpow(int x,int e){int ret=1;for(;e;e>>=1,x=1ll*x*x%MOD)if(e&1)ret=1ll*ret*x%MOD;return ret;}
int n,a[MAXN+5],dp[MAXN+5][MAXN+5];
void solve(){
scanf("%d",&n);
for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=0;
for(int i=1,x,y;i<=n;i++)scanf("%d%d",&x,&y),a[i]=1ll*x*qpow(y,MOD-2)%MOD;
for(int i=0;i<=n;i++)scanf("%d",&dp[0][i]);
for(int i=0;i<n;i++)for(int j=0;j<=n;j++){
if(j){
dp[i+1][j-1]=(dp[i+1][j-1]+1ll*a[i+1]*dp[i][j])%MOD;
if(j<n)dp[i+1][j+1]=(dp[i+1][j+1]+1ll*(1-a[i+1]+MOD)*dp[i][j]%MOD);
}else{
dp[i+1][0]=(dp[i+1][0]+1ll*(1-a[i+1]+MOD)*dp[i][j])%MOD;
dp[i+1][1]=(dp[i+1][1]+1ll*(1-a[i+1]+MOD)*dp[i][j])%MOD;
}
}
for(int i=1;i<=n;i++)printf("%d%c",dp[i][0]," \n"[i==n]);
}
int main(){
int qu;scanf("%d",&qu);while(qu--)solve();
return 0;
}