经典套路。
题意
你将随机生成一个长度为 \(k\) 的数组 \(a\)，其中 \(a_i\) 有 \(p_i\) 概率为 \(1\)，否则为 \(-1\)。定义其前缀和数组 \(s_i = \sum\limits_{j = 1}^{i}a_j, i \in [0, k]\)。如果前缀和数组的最大值为 \(t(t \in [0, k])\) 那么你将获得 \(h_t\) 的权值。给定数组 \(p_{1 \dots n}, h_{1 \dots n}\)，对于所有 \(k = 1 \dots n\)，请输出你获得权值的数学期望。对 \(10^9+7\) 取模。
数据范围：\(1 \le n \le 5000, 0\le h_i \le 10^9\)。
做法
考虑直接 DP，那么你必须记录当前值和先前的最大值两个信息，状态是 \(\Theta(n^3)\) 的，埋了。接下来考虑容斥，考虑了一年，没做出来。怎么办呢？
首先将问题抽象为一个二维平面上随机生成一串线段，要么向上斜要么向下斜，然后头尾接起来形成的形状的最高点是要考虑的东西。你可以联想到那种一排矩形的问题可以竖过来一层一层 DP。这里同理。不要考虑当前这一步在先前积累下的影响下要怎么走，而是去考虑在开头添加一步对后面的影响。那么我只关心后面的最高高度，它会被平移一下；而当前位置的高度是确定的——\(0\)。这样就好办了，直接倒过来 DP 就行了。
但是很不幸你必须枚举 \(f_{k, 0} = 1\) 作为转移起点再 DP，这样还是三方。但是没关系，我们发现最终状态是确定且唯一的。所以直接把 DP 转移的方向也全部倒过来，把系数 \(h_i\) 填到 \(f_{0, i}\) 作为初始状态，然后对于每个 \(k\) 统计 \(f_{k, 0}\) 的值即可。
代码
// Author: kyEEcccccc
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)
constexpr int N = 5005, MOD = 1000000007;
LL kpow(LL x, LL k = MOD - 2)
{
x = x % MOD;
LL r = 1;
while (k)
{
if (k & 1) r = r * x % MOD;
x = x * x % MOD;
k >>= 1;
}
return r;
}
int n, po[N];
int f[2][N];
void work(void)
{
cin >> n;
F(i, 1, n)
{
int x, y; cin >> x >> y;
po[i] = x * kpow(y) % MOD;
}
F(i, 0, n) cin >> f[0][i];
int ci = 1, pi = 0;
F(i, 1, n)
{
F(j, 1, n - i)
{
f[ci][j] = ((LL)f[pi][j + 1] * po[i]
+ (LL)f[pi][j - 1] * (1 - po[i] + MOD)) % MOD;
}
f[ci][0] = ((LL)f[pi][1] * po[i]
+ (LL)f[pi][0] * (1 - po[i] + MOD)) % MOD;
cout << f[ci][0] << " \n"[i == n];
swap(ci, pi);
}
}
signed main(void)
{
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(nullptr);
int _; cin >> _;
while (_--) work();
return 0;
}