场上的我像个 sb

Erine · 2025-11-03 09:49:52 · 题解

令 s_i 的状态为一个集合 U=\{i\mid s_i=1\}。考虑确定一个 S\subseteq U，|S|\ge m 使得 S 内的元素恰好录用，非 S 内的元素都不被录用。

此时，我们有限制：

• 对于 i\in S，要求 c_i\gt \sum_{j=1}^{i-1}[j\not\in S]；
• 对于 i\not \in S，要求 c_i\le \sum_{j=1}^{i-1}[j\not\in S]。

发现是两个相反方向的限制，考虑对第一个容斥。具体地，我们钦定一个集合 T\subseteq S，令 i\in T 的限制不合法，i\not\in T 不做任何限制，容斥系数为 (-1)^{|T|}。那么此时，所有限制被转化为了统一的形式。

而对于这种统一形式的限制的方案数是容易计算的：注意到 i 递增时，\sum_{j=1}^{i-1}[j\not\in S] 同样递增，因此我们从左到右扫一遍，对于所有 i\in T\cup (U/S) 的 i，计算其 c_i 可取的方案数，再扣掉前面选过的个数，因为前面的取值集合被当前的完全包含。而其余的 i 没有要求，可以乱填，最后再乘上阶乘即可。

此时，直接可以考虑设计 dp：f_{i,j,k} 表示，前 i 个数，钦定 j 个数在 S 中，k 个数在 T 中。转移是简单的，统计答案同样是简单的。

复杂度三次方，需要滚动数组。