考虑一个什么样的序列合法，通过观察得到结论：

定义第 $i$ 位合法为 $b_i \le b_{i-1}+b_{i+1}$，一个序列合法，当且仅当其所有位合法。

必要性是显然的，$b_i$ 最多会被减 $b_{i-1}+b_{i+1}$，然后 $b_{i-1}$，$b_{i+1}$ 就都变为 $0$，此时无解。

证明必要性，对于一组符合结论的序列，我们找到第一个 $b_i > b_{i+1}$，再将 $[1,i-1]$ 的 $b_i$ 全部减成 $0$，这样得到的序列依然符合结论。

这样我们容易设计出 dp。设 $f_{i,j,k}$ 为考虑前 $i$ 位，$b_i = j, b_{i-1}= k$ 的合法方案数，使用前缀和优化即可。

注意，$f_i$ 的合法指的是 $[1,i-1]$ 位合法，最后得到的答案为 $\sum f_{n+1,0,x}$。

时间复杂度 $O(n^3)$，可以通过 D1。

尝试优化，由于状态数已经是 $O(n^3)$，我们必须精简状态。

设 $f_{i,j}$ 为考虑前 $i$ 位，$b_i= j$ 的合法方案数，转移时枚举第 $i$ 位和第 $i-2$ 位，这样使 $i-1$ 位合法的方案数就是固定的。

$f_{i,j} = \sum\limits_{x=0}^k f_{i-2,x} \times (x+j+1)$。

但是这样转移会有个大问题，我们能确保 $i-1$ 位合法，但 $i-2$ 位可能不合法，因此这样转移不可行。

正难则反，考虑容斥，用前 $i-1$ 位合法的方案数减去前 $i-2$ 位合法，第 $i-1$ 位不合法的方案数。

因为有如下性质：若第 $i$ 位不合法，则第 $i-1$ 位一定合法。

证明：$b_i > b_{i-1}+b_{i+1},b_{i-1} > b_i+b_{i-2} \rightarrow b_{i+1}+b_{i-2} < 0$，矛盾。

因此如果反着转移，就可以解决刚才的问题。

使用前缀和优化，时间复杂度 $O(n^2)$。