[CSP-S 2025] 员工招聘 / employ

P14364 [CSP-S 2025] 员工招聘 / employ

先初步分析一下录取的条件：

• \(s_i=0\) 此时一定不会被录取
• \(s_i=1\) 记之前被淘汰的人数为 \(j\)，则若 \(c_{p_i}>j\) 则会被录取，\(c_{p_i}\le j\) 不会被录取。

考虑一个从前往后的 \(\mathrm{dp}\)，\(f_{i,j}\) 表示填好了 \(p_{1\sim i}\)，且有 \(j\) 个人被淘汰的方案数。但是这样需要考虑前面被用掉的 \(c\) 对后面的影响。

贡献延后计算

考虑再记一维，\(f_{i,j,k}\) 表示填好了 \(p_{1\sim i}\)，且有 \(j\) 个人被淘汰的方案数此时有 \(k\) 个位置满足 \(c_{p_i}>j\)。转移较为复杂，记 \(cnt_j\) 表示 \(c_i=j\) 的个数，\(s_j\) 表示 \(c_i\le j\) 的个数，转移时分类讨论：

• 这个人来面试 \((c_{p_i}>j)\)

  • \(s_i=1\)。 录取 \(p_i\)，那么需要满足 \(c_{p_i}>j\)，但是我们并不知道具体方案数，考虑将贡献延后计算，在 \(j\) 往后不断增加的过程中，我们在 \(c_{p_i}=j+1\) 的位置计算上当前位置的放置方案数，即先不算上放上这个位的方案数，得到 \(f_{i+1,j,k+1}\leftarrow f_{i,j,k}\)。

  • \(s_i=0\)。无法录取 \(p_i\)，应当转移到 \((j+1,k+1)\)，不过别忘了要算上之前 \(c_{p_i}=j+1\) 的位置，枚举有 \(\ell\) 个位置等于 \(j+1\)，将这些位置分配给 \(k+1\) 个位置，方案数 \(\binom{k+1}{\ell}\)，选出这些位置有 \(\binom{cnt_{j+1}}{\ell}\) 种选法，分配完之后这些数可以乱排，因此最终得到转移：

    \[f_{i+1,j,k+1-\ell}\leftarrow \binom{k+1}{\ell}\binom{cnt_{j+1}}{\ell}\ell!\times f_{i,j,k} \]

• 这个人不来面试 \((c_{p_i}\le j)\)

  这个人一定不会被录取，贡献到 \((j+1,k)\)，需要算上当前位的 \(p_i\) 方案数，总共有 \(s_j\) 种选择，但是之前已经有 \((i-k)\) 个被选过了，因此当前位方案数为 \([s_j-(i-k)]\)。同时要类似算上 \(c_{p_i}=j+1\) 的贡献：

  \[f_{i+1,j+1,k-\ell}\leftarrow [s_j-(i-k)]\binom{k}{\ell}\binom{cnt_{j+1}}{\ell}\ell!\times f_{i,j,k} \]

考虑答案的计算，到 \(f_n\) 处所有的位置都放好了，直接枚举有 \(j\) 个人寄掉即可，那么自然 \(c_{p_i}>j\) 的位置就有 \(k=n-s_j\) 个，但是由于贡献延后计算的影响，这些位置还没有计算乱排的方案，于是答案为

\[\sum_{j=0}^{n-m} f_{n,j,n-s_j} (n-s_j)! \]

分析一下时间复杂度，看似是 \(O(n^4)\) 的，但是其实每次枚举的 \(\ell\le cnt_j\)，其和是 \(O(n)\) 的，因此总时间复杂度是 \(O(n^3)\) 的，常数较大，不过可以通过。

容斥

上述贡献延后计算的做法太繁琐复杂，我们将重心从排列本身转到最终每个人的状态上，显然我们最后只是关注有多少个人面试成功了，因此可以枚举最终面试的状态 \(a\)，\(a_i=0/1\) 表示 \(p_i\) 是否面试成功。则我们可以对每个 \(a\) 计算出满足的排列 \(p\) 的数量。考虑令 \(f_{i,j,k}\) 表示填好了 \(a_{1\sim i}\)，有 \(j\) 个人面试失败，且钦定有 \(k\) 个位置已固定时计算上的贡献。转移依旧分类讨论：

• \(s_i=0\)。 此时一定 \(a_i=0\)：\(f_{i+1,j+1,k}\leftarrow f_{i,j,k}\)。

• \(s_i=1\)。

  • 令 \(a_i=0\)。\(f_{i+1,j+1,k+1}\leftarrow f_{i,j,k}\times (s_j-k)\)。

  • 令 \(a_i=1\)。此处需要计算 \(c_{p_i}>j\) 的方案数，这个不好算，但是我们可以容斥，用总方案数减去存在 \([c_{p_i}\le j]\) 的方案数。总方案数就是不对此处做出钦定，\(f_{i+1,j,k}\leftarrow f_{i,j,k}\)。

    容斥掉钦定 \([c_{p_i}\le j]\) 的方案数，得到 \(f_{i+1,j,k+1}\leftarrow -f_{i,j,k}\times (s_j-k)\)。

最后是答案的计算，枚举 \(j\le n-m,k\)，由于有 \(k\) 个位置已经固定，剩下的可以任意排列，方案数为 \((n-k)!\)，因此不难得到答案为：

\[\sum_{j=0}^{n-m}\sum_{k=0}^{n} f_{n,j,k}(n-k)! \]

时间复杂度 \(O(n^3)\)，非常简洁。