题解：P14364 [CSP-S 2025] 员工招聘 / employ（暂无数据）

· · 题解

考虑从左往右进行填数，并且记录当前已经有多少个没有被录用的人。

初步令 dp_{i,j} 为填完第 i 个人的时候，有 j 个人没有录用的方案数。此时会分成两类人：第一类是 c \le j 的——一定不会被录用。第二类是 c > j 的：只有 s_i=0 的时候才不会被录用。

令 S_i 为有多少个人的 c \le i，T_i 为有多少个人的 c=i。

发现这玩意会假掉，毕竟你没法假定你需要从多少个第二类人中选一个。于是考虑这样的策略：每次要么填一个第一类人，要么填一个“空穴”，之后在第二类人转化为第一类人的时候往空穴里面补。

状态：令 dp_{i,j,k} 为填完第 i 个人之后，有 j 个没有录用，有 k 个空穴的方案数。

转移：

  1. s_i=1

此时要么选择一个第一类人让没有被录用的人数 +1：

dp_{i+1,j+1,k-l} \leftarrow (S_i-(i-k))\binom{k}{l}\binom{T_{j+1}}{l}l!dp_{i,j,k}

要么填入一个空穴：

dp_{i+1,j,k+1} \leftarrow dp_{i,j,k}
  1. s_i=0

要么选择一个第一类人：

dp_{i+1,j+1,k-l} \leftarrow (S_i-(i-k))\binom{k}{l}\binom{T_{j+1}}{l}l!dp_{i,j,k}

要么填入一个空穴：

dp_{i+1,j+1,k-l+1} \leftarrow \binom{k+1}{l}\binom{T_{j+1}}{l}l!dp_{i,j,k}

注意顺序可以认为：先填写，再填穴。此时上面转移的 l 的范围可以达到 k+1。

统计答案的时候，当没有被雇佣的人数达到 j 的时候，c 在 [j+1,n] 的所有人都没有考虑到。此时应该有 (S_n-S_j) 个空穴让其填入，于是答案为：

\sum \limits_{i=m}^{n} dp_{n,i,S_n-S_i}(S_n-S_i)!

注意到对于一个 dp_{i,j,*} 而言，合法的 l 至多 O(T_{j+1}) 个，而 \sum T_j=n，所以对于 dp_{i,*,*} 而言，合法的转移是 O(n^2) 级别的。于是时间复杂度为 O(n^3)。

#include<bits/stdc++.h>

using namespace std;

#define int long long

constexpr int maxn=500;
constexpr int mod=998244353;

int dp[2][maxn+5][maxn+5];
int c[maxn+5];
int sum[maxn+5];
int ton[maxn+5];
string s;
int n,m;

int frac[maxn+5];
int inv[maxn+5];

int ksm(int a,int b){
    int ans=1;
    while(b){
        if(b&1){
            ans=ans*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

void veradd(int& x,int y){
    x=x+y-(x+y>=mod)*mod;
}

int add(int x,int y){
    return x+y-(x+y>=mod)*mod;
}

int binom(int n,int m){
    return frac[n]*inv[m]%mod*inv[n-m]%mod;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n>>m;
    frac[0]=1;
    for(int i=1;i<=n;i++){
        frac[i]=frac[i-1]*i%mod;
    }
    inv[n]=ksm(frac[n],mod-2);
    for(int i=n-1;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
    cin>>s;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        ton[x]++;
    }
    sum[0]=ton[0];
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+ton[i];
    }
    dp[0][0][0]=1;
    for(int i=0,p=0;i<n;i++,p^=1){
        for(int j=0;j<=i;j++){
            for(int k=0;k<=i;k++){
                if(!dp[p][j][k]){
                    continue;
                }
                if(s[i]=='1'){
                    veradd(dp[p^1][j][k+1],dp[p][j][k]);
                    for(int l=0;l<=min(k,ton[j+1]);l++){
                        veradd(dp[p^1][j+1][k-l],dp[p][j][k]*binom(k,l)%mod*binom(ton[j+1],l)%mod*frac[l]%mod*(sum[j]-(i-k))%mod);
                    }
                }
                else{
                    for(int l=0;l<=min(k+1,ton[j+1]);l++){
                        veradd(dp[p^1][j+1][k+1-l],dp[p][j][k]*binom(k+1,l)%mod*binom(ton[j+1],l)%mod*frac[l]%mod);
                    }
                    for(int l=0;l<=min(k,ton[j+1]);l++){
                        veradd(dp[p^1][j+1][k-l],dp[p][j][k]*(sum[j]-(i-k))%mod*binom(k,l)%mod*binom(ton[j+1],l)%mod*frac[l]%mod);
                    }
                }
            //  cout<<i<<" "<<j<<" "<<k<<" "<<dp[p][j][k]<<"\n";
                dp[p][j][k]=0;
            }
        }
    }
    int ans=0,sm=0;
    for(int i=n;i>=0;i--){
        if(i<=n-m){
            veradd(ans,dp[n&1][i][sm]*frac[sm]%mod);
        }
        sm+=ton[i];
    }
    cout<<ans;
}