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

HRS_ren_zheng_hang · 2025-11-01 23:20:22 · 题解

观察数据范围发现可以 O(n^3)，考虑dp。

设 dp_{i,j,k} 表示已经过了 i 天，已经有 j 个人被拒绝或放弃，前 i 天中有 k 个人满足 c_k\le j 时的方案数，不考虑 c_i> j 的人之间的差别。

设 cnt_i 表示，pre_i 表示其前缀和。

考虑从 dp_{i,j,k} 转移：

• 若 s_{i+1}=0

  显然要转移到 dp_{i+1,j+1,k^\prime}（k^\prime 的范围有多个限制，详见代码）

  先不考虑第 i+1 天的人，由于之前没有区分 c_i=j+1 的人和 c_i> j+1 的人，现在需要另外计算这部分的贡献，即 new=dp_{i,j,k}\times \begin{pmatrix} i-k \\ k^\prime-k \end{pmatrix}\begin{pmatrix} cnt_{j+1} \\ k^\prime-k \end{pmatrix}(k^\prime-k)!（如果dp状态时考虑了所有人的差别，这里就不好转移），然后根据第 i+1 天的人分类讨论：

  • \le j+1$，$dp_{i+1,j+1,k^\prime+1}\leftarrow new\times (pre_{j+1}-k^\prime)
  • > j+1$，$dp_{i+1,j+1,k^\prime}\leftarrow new

• 若 s_{i+1}=1

  这次先分类讨论：

  • > j$，直接 $dp_{i+1,j,k}\leftarrow dp_{i,j,k}
  • \le j$，和上面一样处理后 $dp_{i+1,j+1,k'+1}\leftarrow new\times (pre_j-k)

注意计算答案时要算上未区分的人的贡献。

时间复杂度：

• 转移复杂度 O(cnt_{j+1})，而 \sum cnt_j=n，所以总复杂度 O(n^3)，可以通过本题。

空间用类似01背包的方式去掉一维即可。

代码

有一些边界情况要注意

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353,N=505;
long long f[N],g[N],inv[N];
int n,m,cnt[N],pre[N],dp[N][N];
char s[N];

int main()
{
    scanf("%d %d",&n,&m);
    f[0]=f[1]=g[0]=g[1]=inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        f[i]=f[i-1]*i%mod;
        inv[i]=inv[mod%i]*(mod-mod/i)%mod;
        g[i]=g[i-1]*inv[i]%mod;
    }
    scanf("%s",s+1);
    for(int i=1,c;i<=n;i++)
    {
        scanf("%d",&c);
        cnt[c]++;
    }
    pre[0]=cnt[0];
    for(int i=1;i<=n;i++)pre[i]=pre[i-1]+cnt[i];
    dp[0][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=i;j>=0;j--)
        {
            for(int k=pre[j];k>=0;k--)
            {
                int now=dp[j][k];
                dp[j][k]=0;
                if(s[i+1]=='0')
                {
                    for(int k2=max(k,i-(n-pre[j+1]));k2<=k+cnt[j+1]&&k2<=i;k2++)
                    {
                        const int tot=i-k,ths=k2-k,num=cnt[j+1];
                        const long long x=f[tot]*g[ths]%mod*g[tot-ths]%mod*f[num]%mod*g[num-ths]%mod;
                        if(j+1!=n&&pre[j+1]-k2!=n-i)dp[j+1][k2]=(dp[j+1][k2]+x*now)%mod;
                        dp[j+1][k2+1]=(dp[j+1][k2+1]+x*now%mod*(pre[j+1]-k2))%mod;
                    }
                }
                else
                {
                    for(int k2=max(k,i-(n-pre[j+1]));k2<=k+cnt[j+1]&&k2<=i;k2++)
                    {
                        const int tot=i-k,ths=k2-k,num=cnt[j+1];
                        const long long x=f[tot]*g[ths]%mod*g[tot-ths]%mod*f[num]%mod*g[num-ths]%mod;
                        dp[j+1][k2+1]=(dp[j+1][k2+1]+x*now%mod*(pre[j]-k))%mod;
                    }
                    if(pre[j]-k!=n-i)dp[j][k]=now;
                }
            }
        }
    }
    int ans=0;
    for(int j=0;j<=n-m;j++)
    {
        const int k=pre[j];
        ans=(ans+dp[j][k]*f[n-k])%mod;
    }
    printf("%d",ans);
    return 0;
}