员工招聘 CSP-S 2025

[CSP-S 2025] 员工招聘

切掉了 /cy

题目链接： [CSP-S 2025] 员工招聘 。

题目描述：

有 $n$ 个数，第 $i$ 个数为 $c_i$ 。还有一个长度为 $n$ 的 $01$ 串 $s$ 。

一个长度为 $n$ 的排列 $p$ 合法当且仅当：

• 依次考虑 $i=1,2,\cdots,n$ 并初始化计数器 $C=0$。
• 若 $c_{p_i}\le C$ 或 $s_i=0$ ，则 $C+1\to C$ 。
• 若最终 $C\le n-m$ ，则排列 $p$ 合法。

求有多少种合法的排列 $p$ ，对 $998244353$ 取模。

$n\le 500$ 。

定义 $f_{i,j,k}$ 为考虑 $s$ 的前 $i$ 个字符，有 $j$ 个数使得 $C+1\to C$ ，有 $k$ 个数满足他们的 $c$ 比 $j$ 大且不考虑这些数具体是什么的合法排列数。

设 $cnt_j$ 表示 $c_i=j$ 的 $i$ 的个数， $sum_j$ 为 $cnt_j$ 的前缀和。

不妨分类讨论一下。

Case #1: $s_i=0$

这种情况下必然有 $C+1\to C$ 。即 $j$ 必定会增大 $1$ 。

由于 $j$ 变为 $j+1$ ，所以 $k$ 的含义变为了 $c$ 大于 $j+1$ 的数，所以要把恰好等于 $j+1$ 的数的排列贡献加入。

设有 $l$ 个数字满足他们的 $c$ 恰好为 $j+1$ ，则共有 $\displaystyle\binom{cnt_{j+1}}{l}\binom{k}{l}l!$ 种方案。其中 $\displaystyle\binom{cnt_{j+1}}{l}$ 的含义是从恰好满足 $c$ 为 $j+1$ 的数中选择 $l$ 个； $\displaystyle\binom{k}{l}l!$ 表示从原来没有确定具体内容的 $k$ 个位置（因为其他 $i-k$ 个位置已经确定了）选择有顺序的 $l$ 个。

则我们可以分类讨论：

Case #1.1

若 $i+1$ 的数 $p$ 满足 $c_p\le j+1$ ，则有：

$$(sum_{j+1}-(i-(k-l)))\binom{cnt_{j+1}}{l}\binom{k}{l}l!f_{i,j,k}\to f_{i+1,j+1,k-l}$$

Case #1.2

若 $i+1$ 的数不满足 Case #1.1 ，则：

$$\binom{cnt_{j+1}}{l}\binom{k}{l}l!f_{i,j,k}\to f_{i+1,j+1,k-l+1}$$

Case #2: $s_i=1$

同样的，分类讨论。

Case #2.1

若 $i+1$ 的数 $p$ 满足 $c_p\le j$ ，则有：

$$(sum_j-(i-k))\binom{cnt_{j+1}}{l}\binom{k}{l}l!f_{i,j,k}\to f_{i+1,j+1,k-l}$$

Case #2.2

若 $i+1$ 的数不满足 Case #2.2 ，则有：

$$f_{i,j,k}\to f_{i+1,j,k+1}$$

然后就没了，模拟就行。