菜王的 blog

在阅读本篇题解之前，请阅读 [USACO24JAN] Cowmpetency S 题解（或者洛谷博客链接）。

首先考虑一个 $O(nc^2)$ 的暴力 dp：设 $f_{i, j}$ 表示目前考虑 $a$ 前 $i$ 项，前缀 $\max = j$ 的方案数。转移方程显然：

$f_{i, j} \gets \begin{cases} j \times f_{i - 1, j} & b_i = -1\\ j \times f_{i - 1, k} (k \le j) & b_i = 0\\ j \times f_{i - 1, k} (k < j) & b_i = 1\\ \end{cases}$

可以前缀和优化至 $O(nc)$。

我们发现，如果将 $b$ 中连续的 $0, -1$ 缩成一段，则段数是 $O(q)$ 的，而连续的一段 $0, -1$ 可以一起计算。设第 $i$ 段元素为 $b_i$，长度为 $c_i$（当 $b_i = 1$ 时 $c_i = 1$），$f_{i, j}$ 表示目前考虑前 $i$ 段，前缀 $\max = j$ 的方案数。转移方程考虑讨论当前这一段是否出现了新的前缀最大值：

$f_{i, j} \gets j^{c_i} \times f_{i - 1, j} (b_i \ne 1)\\ f_{i, j} \gets g_{c_i}(x) \times f_{i - 1, k} (k < j, b_i \ne -1)\\$

其中 $g_y(x)$ 为 $y$ 个 $[1, x]$ 的整数至少有一个为 $x$ 的方案数，用任意情况减去一个 $x$ 都没有的情况可以推出 $g_y(x) = x^y - (x - 1)^y$。

可以前缀和优化至 $O(qc \log n)$，代码在这里。