[USACO24JAN] Cowmpetency G 题解
vegetable_king
·
·
题解
可能更好的阅读体验
在阅读本篇题解之前，请阅读 [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)，代码在这里。