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

Lehe · 2025-11-01 23:20:04 · 题解

好像是正赛场切过的最牛的题。

考虑 dp。先考虑设 f_{i,j} 表示前 i 天寄了 j 个人的方案数。但是发现我们要往后填的时候，我们不知道此时还有哪些数能用，比较倒闭。而且这个也很难塞到状态里。

上述做法做不了的本质是，我们前面决策选了后面的哪个 c_x 会对后面每个时刻能选的数产生影响。因此我们考虑一个经典 trick：贡献延后计算。具体地，我们可以考虑不在加入一个人时就计算它的方案数，而是留到后面“有用”时再来计算。由于每个时刻一个人 k 能不能成功，本质上只与是否 c_x > j 有关，因此我们自然想到在 j 增加到第一次 c_x = j 时去考虑其贡献。

我们加入一维 k，f_{i,j,k} 表示前 i 天寄了 j 个人，当前有 k 个满足 c_x>j 的人已经被面试过。k 的本质就是我们提前钦定了多少个位置，现在还剩这么多要在后面再填回去。

考虑转移：

当前的人来面试，且面试成功（c_x > j 且 s_i = 1）：此时我们知道需要在这里填一个 c_x>j 的人，但是我们不知道是谁。因此是

f_{i,j,k} \to f_{i+1,j,k+1}

当前的人来面试，且面试失败（c_x > j 且 s_i = 0）：此时 j 应当增加 1，同时因为来参加面试了所以这个人也得满足 c_x > j，k 也得增加 1。根据我们之前的分析，这时候还应当考虑计算所有被提前钦定的 c_x = j+1 的贡献，因此我们枚举前面用了 l 个 c_x = j+1，这时候一共有 k+1 个待填的空所以是 \binom{k+1}{l}，同时还要从所有 c_x = j+1 的人里面选 l 个出来排列，记人数为 cnt_{j+1}，则转移式为

f_{i,j,k} \times \binom{k+1}{l} \times \binom{cnt_{j+1}}{l} \times l! \to f_{i+1,j+1,k+1-l}

当前的人玉玉了不来面试（c_x \le j）：其实与上一种转移很像。不过由于他得满足 c_x \le j 所以我们还得额外从已经不可能来的人里选一个幸运选手出来。这个其实也是容易直接得出的，记录 pre_j 为 c_x \le j 的人数，则我们有可能被选中的人数为 pre_j - (i-k)，其中 i-k 为已经在前几天就被确定了的但是 c_x \le j 的人数。

f_{i,j,k} \times (pre_j-(i-k)) \times \binom{k}{l} \times \binom{cnt_{j+1}}{l} \times l! \to f_{i+1,j+1,k-l}

最后我们只需要枚举有几个人寄了即可，答案为

\sum_{j=0}^{n-m}f_{n,j,n-pre_j} \times (n-pre_j)!

还有一个问题：转移要枚举 l，这个不是 O(n^4) 的吗？仔细想想就会发现由于 l 不可能超过 cnt_{j+1}，而对于固定的 i 和 k，cnt_{j+1} 的和不超过 n，所以其实是 O(n^3) 的。

记得滚动数组。

赛后回忆随手写的丑陋的代码，细节与题解略有出入，仅供参考：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define fir first
#define sec second
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define pb push_back
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
int n,m,dp[2][510][510],fac[510],C[510][510],P[510][510],ans;
string s;
int c[510],rm[510]; 
signed main()
{
    cin>>n>>m>>s;
    s=" "+s;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        c[x]++;
        for(int j=0;j<x;j++)rm[j]++;
    }
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
    for(int i=0;i<=n;i++)
    {
        C[i][0]=1;
        for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        for(int j=0;j<=i;j++)P[i][j]=C[i][j]*fac[j]%mod;
    }
    dp[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        memset(dp[i&1],0,sizeof(dp[i&1]));
        bool ps=s[i]-'0';

        for(int j=0;j<i;j++)if(j<=n-m)
            for(int k=0;k<i;k++)
            {
                int tx=c[j+1];
                int tmp=dp[i&1^1][j][k];
                if(!tmp)continue;
                if(ps)(dp[i&1][j][k+1]+=tmp)%=mod;
                int pr=(n-rm[j])-(i-1-k);
                if(pr)for(int l=min(k,tx);~l;l--)(dp[i&1][j+1][k-l]+=tmp*pr%mod*C[k][l]%mod*P[tx][l]%mod)%=mod;
                if(!ps)for(int l=min(k+1,tx);~l;l--)(dp[i&1][j+1][k+1-l]+=tmp%mod*C[k+1][l]%mod*P[tx][l]%mod)%=mod;
            }
    }
    for(int i=0;i<=n-m;i++)(ans+=dp[n&1][i][rm[i]]*fac[rm[i]]%mod)%=mod;
    cout<<ans<<endl;
    return 0;
}