CF1919E 题解

· · 题解

考虑一个很类似的题。我们把正数和负数分开来考虑，最后用 0 连接一些连续段，形如 0 - \text{正} - 0 - \text{正} - 0 - \text{负}。

先考虑正数。设 f_{i, j} 为考虑了 \ge i 的正数，形成了 j 个连续段的方案数。设 i 的出现次数为 c_i。

那么之前的每个段两端都需要接一个 i 下来，两段之间也可以只用一个 i 连接。

特别地，如果已经考虑到了结尾位置 n，右端不用接数。于是我们状态再记一个 f_{i, j, 0/1} 表示包含位置 n 的段是否出现。

那么对于 f_{i + 1, j, 0} 的转移，新的段数 k = c_i - j 可以直接被计算出来。转移系数是 c_i 个数分配给 j + 1 个空的插板。我们有：

f_{i, k, 0} \gets f_{i + 1, j, 0} \times \binom{c_i - 1}{j} f_{i, k, 1} \gets f_{i + 1, j, 0} \times \binom{c_i - 1}{j}

对于 f_{i + 1, j, 1} 的转移，新的段数为 k = c_i - j + 1。有转移：

f_{i, k, 1} \gets f_{i + 1, j, 1} \times \binom{c_i - 1}{j - 1}

同样地考虑负数，设 g_{i, j} 为考虑了 \le -i 的负数，形成了 j 个连续段的方案数。转移类似。

计算答案，只用枚举正数的段数 i，如果 0 不为 n 的前缀和，那么负数的段数为 c_0 - i，否则为 c_0 - i - 1。讨论一下 n 的前缀和是给 0，正数还是负数，再乘上给段选择位置的系数。所以：

ans = \sum\limits_{i = 0}^{c_0} f_{1, i, 1} \times g_{1, c_0 - i, 0} \times \binom{c_0 - 1}{i - 1} + f_{1, i, 0} \times g_{1, c_0 - i, 1} \times \binom{c_0 - 1}{i} + f_{1, i, 0} \times g_{1, c_0 - i - 1, 0} \times \binom{c_0 - 1}{i}

直接计算 f, g 复杂度为 O(n^2)。但是注意到 f, g 初值只有 O(1) 个位置有值，每次转移一个位置会转移到固定的另一个位置，最后一维只会进行 0 \to 1 的转移不会进行 1 \to 0 的转移。所以 dp 数组每行有值的位置数是 \color{red}{O(1)} 的。如果我们用 unordered_map 把有值的位置存下来，复杂度将是 \color{red}{O(n)}。

code