[ARC117E] Zero-Sum Ranges 2 题解

DengDuck · 2023-11-30 23:08:53 · 题解

upd:更正笔误。

不会简单计数题，加训！

首先普遍的想法是考虑对于一个已知序列怎么快速统计答案。

求前缀和数组 s，设 b_i 表示存在多少 x 满足 s_x=i。

则答案为：

注意到每一种前缀和是独立的，数字是 +1 和 -1，所以前缀和每次要么上一层，要么下一层，变成这个样子：

我们考虑分层做动态规划，从下到上还是从上到下？从上到下。

因为最后合法的数列满足左右两边的值都是 0，为了满足这一点，对于合法的数列，每次加入一层的时候，两边都一定是新加的层的那个值。

你发现，从上到下加层，你就可以比较容易地满足这一点，是的，这让人很爽，动态规划比较自然，然后你就舒服了。

从上向下加层的图可以参考以下这张：

然后我们思考加上下一层怎么加，注意到上一次这些相邻的值，还有两边的间隙了吗？这就是我们放东西的地方。

所以这个时候就可以比较自然地想到状态了，设 f_{i,j,k} 表示目前加的层里我一共放了 i 个点，产生了j 个区间和为 0 个区间，有 k 个间隙（两边的咱们不算，反正你知道那个东西存在，特殊的东西特殊处理）。

初始化就是枚举第一层有几个点就行了。

考虑转移，枚举这一层放 x 个点：

其中 \binom{x-1}{k+1} 是考虑怎么把这 x-1 个点放进间隙中，有这么多方案数，这是一个插板法，你有 k+1 块板子，因为你有 k+2 个间隙，相当于 k+2 个盒子。

然后你有 x 个球，所以有 x-1 个可以插的间隙，这就是一个经典的组合数学问题。

然后直接求就行了，放个图大概更好理解：

最后你发现，前缀和可以是负数啊！可是你这个状态 0 就是最后一层了。

怎么办？做法假了？

没有关系，大力枚举所有状态，然后对于最后一层的间隙，直接和另外一种方案合并。