P14364 [CSP-S 2025] 员工招聘题解

Coffee_zzz · 2025-11-24 10:47:14 · 题解

设集合 U=\{i \mid s_i=1\}，考虑钦定一个集合 S \subseteq U，满足：

对于所有 i\in S，第 i 个位置的人会被录取，即要求 c_i \gt \sum\limits_{j=1}^{i-1} [j \notin S]；
对于所有 i\in U\setminus S，第 i 个位置的人不会被录取，即要求 c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]。

考虑容斥，把第一个条件的形式与第二个条件统一。具体地，钦定一个集合 T \subseteq S，满足：

对于所有 i \in T，第 i 个位置的人不会被录取，即要求 c_i \le \sum\limits_{j=1}^{i-1} [j \notin S]；
对于所有 i \in S\setminus T，第 i 个位置的人没有要求。

容斥系数为 (-1)^{|T|}。

考虑从前往后 dp。设 f_{i,j,k} 表示，考虑到第 i 个位置，此时一共有 j 个数在 S 中，k 个数在 T 中，且仅考虑 T \cup (U \setminus S) 中的位置填的数的方案数。初始化 f_{0,0,0}=1，设 a_i=\sum\limits_{j=1}^n [c_j \le i]，b_i=\sum\limits_{j=1}^i [s_j=1]，考虑转移：

若 s_{i+1}=0，f_{i+1,j,k} \leftarrow f_{i,j,k}；
若 s_{i+1}=1：
- 令 i+1 \in U\setminus S，f_{i+1,j,k} \leftarrow f_{i+1,j,k}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)；
- 令 i+1 \in S\setminus T，f_{i+1,j+1,k} \leftarrow f_{i+1,j+1,k}+f_{i,j,k}；
- 令 i+1 \in T，f_{i+1,j+1,k+1} \leftarrow f_{i+1,j+1,k+1}+f_{i,j,k} \times (a_{i-j}-k-b_i+j)。

其中，系数为 a_{i-j}-k-b_i+j 的原因是：当前位置填的数需要小于等于 i-j，且之前已经用了 k+b_i-j 个这样的数。

答案即为 \sum\limits_{j=m}^n \sum\limits_{k=0}^j f_{n,j,k} \times (-1)^k \times (n-b_n+j-k)!，其中 n-b_n+j-k 是满足 i \notin T \cup (U \setminus S) 的 i 的数量，这些位置上的数可以任意排列。

使用滚动数组优化，空间复杂度 \mathcal O(n^2)，时间复杂度 \mathcal O(n^3)。

const int N=505,mod=998244353;
int n,m,c[N],s[N],a[N],b[N],f[2][N][N],fac[N],ans;
string str;
void add(int &a,int b){
    a+=b;
    if(a>=mod) a-=mod;
}
void solve(){
    cin>>n>>m>>str;
    for(int i=1;i<=n;i++) cin>>c[i],a[c[i]]++;
    for(int i=1;i<=n;i++) s[i]=(str[i-1]=='1'),b[i]=b[i-1]+s[i];
    for(int i=0;i<=n;i++) a[i]+=a[i-1];
    f[0][0][0]=1,fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<n;i++){
        int t=i&1;
        memset(f[t^1],0,sizeof f[t^1]);
        for(int j=0;j<=b[i];j++){
            for(int k=0;k<=j;k++){
                if(s[i+1]==0) add(f[t^1][j][k],f[t][j][k]);
                else{
                    add(f[t^1][j+1][k],f[t][j][k]);
                    int x=a[i-j]-k-b[i]+j;
                    add(f[t^1][j][k],1ll*f[t][j][k]*x%mod);
                    add(f[t^1][j+1][k+1],1ll*f[t][j][k]*x%mod);
                }
            }
        }
    }
    for(int j=m;j<=b[n];j++){
        for(int k=0;k<=j;k++){
            int x=n-b[n]+j-k;
            if(k&1) add(ans,mod-1ll*f[n&1][j][k]*fac[x]%mod);
            else add(ans,1ll*f[n&1][j][k]*fac[x]%mod);
        }
    }
    cout<<ans<<endl;
}

P14364 [CSP-S 2025] 员工招聘 题解

P14364 [CSP-S 2025] 员工招聘题解