P14364 [CSP-S 2025] 员工招聘 / employ（官方数据）(学习笔记)

· · 个人记录

首先考虑m=1的情况

答案为 n!-(一个都不录取的情况数)

所以对于每一个 s_i=1 均有 c_i<=i-1

限制是单调增的，所以可以从前往后一次满足

答案为 $ n! - (n-k)!*\prod(sum_{i-1} - (i-1) )

推广至m不为1的情况

在k个s等于1的位置中，我们需要选出一个集合S(不满足的数量)，使得

  1. |S|<=k-m

  2. 对于 i\in S ,c_i<=t_i(前面放弃的)

  3. 对于不属于S且s为1的情况， c_i>t_i

  4. 剩下任意放

同时有大于和小于，考虑容斥

选出集合T， T\cap S= \emptyset

暴力枚举为 O(3^n) ,考虑用dp转移

$ w_i $ 表示i前面s为0的点 转移为： ```cpp f[i+1][j][k]+=f[i][j][k];//没有任何限制 f[i+1][j+1][k]+=f[i][j][k]*(sum[w[i+1]+j]-j-k);//不符合要求 f[i+1][j][k+1]+=f[i][j][k]*(sum[w[i+1]+j]-j-k);//容斥 `````` 答案为 $$ f_{i,j,k}*(n-j-k)!*(-1)^{k} $$