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

Mr_罗 · 2025-11-02 10:24:43 · 题解

讲一下 jiangly 的做法。

我们假设已经钦定好了每天的人是否录取，设 x_i 表示前缀没录取的总人数。

考察第 i 天的情况：

• - 录取，要求 $c>x_i$。 - 不录取，要求 $c\le x_i$。

这个 c>x_i 有点烦，让我们把它容斥成「任意 {}-[c\le x_i]」。

设 f_{i,j,k} 表示前 i 个人，拒绝了 j 个人，钦定了 k 个人的总方案，转移只需要根据前面算一下就好了，是 3d-0d 的。统计答案也是简单的，时间复杂度 \mathcal O(n^3) 。

::::info[Code 已过民间数据]

int n, m;
char s[N];
int a[N];
Z f[N][N][N];
Z fac[N], inv[N];

void mslv() {
    rd(n, m), rd(s + 1);
    rep(i, 1, n) a[r32]++;
    rep(i, 1, n) a[i] += a[i - 1];
    f[0][0][0] = 1;
    req(i, 0, n) {
        if (s[i + 1] == '0') rep(j, 0, i) rep(k, 0, i)
            f[i + 1][j + 1][k] += f[i][j][k];
        else rep(j, 0, i) rep(k, 0, i) {
            f[i + 1][j][k] += f[i][j][k];
            Z x = a[j] - k;
            f[i + 1][j][k + 1] -= x * f[i][j][k];
            f[i + 1][j + 1][k + 1] += x * f[i][j][k];
        }
    } Z ans;
    rep(j, 0, n - m) rep(k, 0, n) ans += f[n][j][k] * fac[n - k];
    prs(ans);
}

::::