P14364 [CSP-S 2025] 员工招聘 / employ——钦定方案+容斥

li_cat · 2025-11-14 21:47:13 · 个人记录

初见思路

因为是赛题，做到这的时候只剩10min了

直接枚举排列

这题的正解应该是dp

但是直接排列的话不适合dp，因为如果直接枚举每一位放的数的话，就需要存下来已经用了那些数

发现，当以整个排列去划分等价类的时候dp是很困难的

而我们知道集合应当是更适合dp的

所以考虑能不能把一部分排列打包成集合，或者说

钦定一部分位置被选上，然后这个集合的权值就是对应的排列数量

那么考虑钦定完之后的方案

• 原本就是 0 ，那么怎么排都行，直接放到最后拿剩下的随便排
• 钦定了不能过，那么这个时候这里填的c就必须\le s(s为之前被拒掉的人数)
• 钦定了可以过，那么这个时候这里填的c就必须> s，但是这个条件不是很适合排，于是考虑容斥成 随便排-\le s

有了容斥，考虑对一个已有的钦定集合求方案数

那么对于被拒掉的位置，会乘上 cnt(s)-k 的方案数，如果这个值 \le 0 ，就相当于不合法，直接与 0 取 min
( cnt(s) 为 \le s 的 c 的数量, k 是以前排列已经用了的数量)
注意此时并没有记录谁被用了，但是知道上一个用掉的一定也在这一次可以选择的范围里

对于没有被拒绝掉的位置，因为考虑了容斥，又得分成两个集合

• 在第一个集合（随便排）内的元素，直接留到最后随便排
• 在第二个集合的元素，和先前一样排 \le s 的数

直接容斥是 2^n 的，但是这个时候已经可以dp了，对于已用的数的数量一致的情况，增加一个元素意味着容斥系数多乘一个 -1 ，然后再乘一个排 \le s 的数的方案数

但是这样的话可能还得考虑dp套dp

发现这个时候在钦定的基础上我们又对被钦定录取的位置进行了划分，而所有这些划分可以直接被拍扁到整个的枚举中

即所有方案容斥再求和的过程可以直接变成一个 3^n 的三个集合的划分去做类似的容斥

那么发现这样的过程也是可以被拍成dp的，只不过这里还有一个需要的是记录下被拒掉的人的数量

即令 f(i,j,k) 为枚举到第 i 位，前面有 j 个人被拒掉，用掉了 k 的方案数

转移

• 原本就是过不了，所有的 f(i,j,k)->f(i+1,j+1,k)
• 可以过
  • 让过但是容斥里随便排 f(i,j,k)->f(i+1,j,k)
  • 拒掉 令 X=cnt(j)-k ，X\times f(i,j,k)->f(i+1,j+1,k+1)
  • 让过但是容斥里 \le s， -X\times f(i,j,k)->f(i+1,j,k+1)

最后各个状态再把剩下没排的几个数乱排一下乘个 (n-k)! 即可