CF1810G The Maximum Prefix

## 题意

构造一个长度最多为$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\circ}$

现在给定 $n+1$ 个正整数 $h_0,h_1,...,h_n$。$a$ 数组最大前缀和 $S$ 的分数为 $h_{s}$。现在，对于每个 $k$, 你要求
出一个数组长度为$k$ 的期望分数对 $10^9+7$ 取模的结果。
## 解法

首先可以想到很暴力的 $O(n^3)$ 解法。

我们设 $f_{i,j,k}$ 为做到第 $i$ 个位置，当前前缀和为 $j$ 且最大前缀和为 $k$ 。转移式子在此不写。因为我们发现这个解法并优化不了，所以我们需要思考别的方法。

我们思考如果从前往后做不了，不如直接从后往前，那么我们也只需要记录当前最大值就可以了。

设 $f_{i,j} $ 只考虑了 $[i,n]$ 这个区间，最大前缀和为 $j$ 的方案数。因为我们是从后往前枚举的，所以说我们当前缀就是最大前缀，转移式子如下。

$$p_i\times f_{i,j} \to f_{i-1,j+1}$$

$$(1-p_i)\times f_{i,j} \to f_{i-1,max(0,j-1)}$$

但是这样子时间复杂度依旧是 $O(n^3)$ 的，因为我们丢失了单次 $dp$ 可以求出所有答案的性质。

但是我们可以发现，这个 $dp$ 是可以倒着做的。因为我们可以发现，我们每次 $dp$ 的初始值都是 $f_{l,0}=1$ 也就是说我们只是转移次数不一样，系数都是相同的，所以我们可以直接反过来做，求出系数大小就相当于求出答案。

边界情况 $f_{1,i}=d_i$ 。

$$f_{i+1,j}\gets p_i\times f_{i,j+1} +(1-p_i) \times f_{i,max(0,j-1)}$$

最后每个的答案就是 $f_{l,0}$ ，时间复杂度 $O(n^2)$。