ARC117E Zero-Sum Ranges 2

题意 ： 求出满足下列条件的序列 的数目 ：

• 含有 个 和 个 。
• 恰有 个 满足 的和为 。

，，时限。

---

• 参考资料：一类基于笛卡尔树的排列计数DP | Whisper-6's Blog!

考虑 的前缀和 ，记 ，则 就是和为 的区间数目。

考虑从大到小（从下往上，即按照水淹笛卡尔树的顺序）填写 。

记 表示填写了 个位置，目前分为 段，目前填写了 层，且目前的 为 的方案数。

计算答案时，由于强制要求 ，考虑对 和 进行拼接。

具体地，拼接时一定是一段 一段 交错，记 为（由于对称性，正负部分的方案数是一样的）分为 段，占用 个位置， 为 的方案数，则答案为

然后可以发现，我们只关心段数而不关心层数，所以可以将 中的 省去，按照 从大到小转移即可。

对于 ，向上加一层，可能出现下列情况 ：

• 某个段间隙被连接，需要占用一个位置，且会使得两个段合成一个

• 某个段间隙未连接，（由于 的变化连续）需要左右各占用一个位置来扩展

• 加入新的“山谷”

枚举新一层加入数的个数 ，则有 ：

妙处在于 ：共有 个间隙以供插入，考虑每个空位，若只放一个数，则使得两侧合并；若放 个，则先用两个贴在空位两侧，其余使得段数增加 。不难得知新的段数为 。

方案数等价于将 个球放入 个盒子，不允许空盒：

复杂度为 ，可以通过。