[CF2119D] Token Removing 题解

将题意转化一下，即我们要把 个标记中的若干个放到区间 内，且右端点各不相同的方案数。设 表示已经考虑了标记 ，当前还剩 个右端点没有使用的方案数。为什么要倒序遍历呢？因为标记 能使用的右端点，标记 一定能使用。转移分两种情况讨论。

• 若不选择当前这个标记，那么就多出了一个右端点。此时贡献是 。

• 若选择当前这个标记，包含它的区间的左端点有 中情况（），区间右端点有 种情况（原本的 个空余的右端点加上位置 新产生的一个）。此时贡献是 。

所以 ，初始状态是 ，答案是 。

提交记录。