资讯详情

考虑建出大根笛卡尔树，一个数能够被加入 \(a\) 中的充要条件是其左子树或者右子树为空。

设计一个 DP \(f_x\) 表示 \(x\) 子树里的方案，分成以下若干种情况：

• \(x\) 是根节点，这样根节点只能最后删除，贡献是左右子树 DP 数组乘起来，再乘上一个互相交叉选择的组合数。

• \(x\) 的左边界是 \(1\)，意味着其左子树不可能被删完，必须删除完右子树才能删除根节点，组合数 \(\binom{l + r + 1}{l}\)。

• \(x\) 的右边界是 \(n\)，这部分同理。

• \(x\) 无限制，容斥一下，用左边界加右边界的方案数减去最后再删除 \(x\) 的方案数。

最后乘上左右子树贡献即可。