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

首先考虑m=1的情况

答案为

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

所以对于每一个

s_i=1

均有

c_i<=i-1

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

sum_i

表示

c<=i

的数量

答案为

n! - (n-k)!*\prod(sum_{i-1} - (i-1) )

推广至m不为1的情况

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

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

选出集合T，

T\cap S= \emptyset

暴力枚举为

O(3^n)

,考虑用dp转移

f_{i,j,k}

表示前i个s=1的点中，j个属于S，k个属于T

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}

文章操作